Printer Friendly

Efficient Enumeration of Non-isomorphic Interval Graphs.

1 Introduction

Graph enumeration problems, besides their theoretical value, are of interest not only for computer scientists, but also to other fields, such as physics, chemistry, or biology. Enumeration is helpful when we want to verify some hypothesis on a quite big set of different instances, or find a small counterexample. For graphs it is natural to say that two graphs are "different" if they are non-isomorphic. Many papers dealing with the problem of enumeration were published for certain graph classes, see Kiyomi et al. (2006); Saitoh et al. (2010, 2012); Yamazaki et al. (2018). A series of potential applications in molecular biology, DNA sequencing, network multiplexing, resource allocation, job scheduling, and many other problems, makes the class of interval graphs, i.e. intersection graphs of intervals on the real line, a particularly interesting class of graphs. In this paper, we focus on interval graphs, and our goal is to find an efficient algorithm that for a given n lists all non-isomorphic interval graphs on n vertices. It is well-known that the number of such graphs is roughly [n.sup.nc] for some constant c, see Acan (2018); Hanlon (1982); J.C. Yang (2017). For that reason, we measure the efficiency of the enumeration algorithm by the worst-case time delay between output of any two successive graphs.

1.1 Previous work

Yamazaki et al. (2018) presented an enumeration algorithm for non-isomorphic interval graphs that works with the worst-case time delay O([n.sup.6]), and recently Yamazaki et al. (2019) improved it to O([n.sup.4]). Their algorithm is based on the reverse search method, invented by Avis and Fukuda (1996), and in its general form works in the following way. Let C be a family of graphs we want to enumerate, and let [G.sub.1],..., [G.sub.k] [member of] C be some special graphs called roots. We define a family forest F which spans C, and consists of k rooted trees [T.sub.1],..., [T.sub.k] such that the root of [T.sub.i] is [G.sub.i]. For graphs that are not roots, let par :C\{[G.sub.1], ..., [G.sub.k]} [right arrow] C be the parent function. In order to enumerate all graphs in the family C, we enumerate all graphs that belong to each tree independently, and to enumerate all graphs in the tree [T.sub.i] we use any tree traversal algorithm like BFS or DFS. The most time consuming operation in the tree traversal is computing the children of a graph G. From the definition, children of G are those graphs G' [member of] C whose parent is G. Hence, if we want to design a fast enumeration algorithm that uses this technique, we need to carefully define the parent function. Yamazaki et al. (2019) used the fact that for every interval graph G = (V, E) that is not a complete graph, there is at least one edge e such that the graph [G.sub.e] = (V,E[union] {e}) is also an interval graph. They defined the only root [G.sub.1] to be a complete graph on n vertices, and par (G) = [G.sub.e], where the edge e is uniquely defined - for more details see Yamazaki et al. (2019). The consequence of this approach is the fact that for every graph G on n vertices there are at most O([n.sup.2]) candidates for the children of G in F, and so this number does not depend on the size of the enumerated family. Moreover, the authors observed that in order to enumerate only non-isomorphic graphs, it is enough to filter out isomorphic copies from the set of children. Isomorphism test in the class of interval graphs is an easy problem thanks to MPQ-trees, see Section 2. Hence, to compute the set of children for a graph G = (V, E), the authors consider all graphs [G.sub.e] = (V, E \ {e}). For each of them, they check whether [G.sub.e] is an interval graph using some linear time recognition algorithm. Then, if [G.sub.e] is an interval graph, they check whether G = par([G.sub.e]), and build a corresponding MPQ-tree. Finally, they store a set of children trees, effectively removing all duplicates.

1.2 Our results

In this paper we revisit the work of Yamazaki et al. and show how to modify their enumeration algorithm to significantly reduce the worst-case time delay between the output of two successive graphs. Our key observation is the fact that having an MPQ-tree corresponding to a graph G = (V, E) we are able to list all edges e such that a graph [G.sub.e] = (V, E \ {e}) is an interval graph. Moreover, for each such edge we show how to build an MPQ-tree corresponding to the graph [G.sub.e] without constructing it explicitly.

1.3 Organization of this paper

In the next section we introduce concepts and definitions that are widely used in this paper, and also provide a detailed description of MPQ-trees along with their most important properties. In Section 3, we present a total ordering over all MPQ-trees, define a canonical MPQ-tree using this ordering, and also present a fast algorithm that for a given MPQ-tree T computes its canonical form T'. In Section 4 we consider an MPQ-tree T corresponding to an interval graph G = (V, E), and characterize edges e such that the graph [G.sub.e] = (V, E \ {e}) is also an interval graph. Moreover, for every edge e we either show a linear time algorithm that produces a string representing [G.sub.e] if it is an interval graph, or show an induced chordless cycle on four vertices or an asteroidal triple in [G.sub.e] that certifies that [G.sub.e] is not an interval graph. In Section 5 we develop data structures and algorithms that make use of combinatorial characterization from Section 4 and present a fast algorithm which for a given MPQ-tree lists all edges e such that [G.sub.e] is an interval graph. Finally, in Section 6 we show how to combine all parts together and build the graph enumeration algorithm. We also show the worst-case performance analysis of our algorithm in this section. The last section contains a discussion of some implementation heuristics that do not change the worst-case analysis, but significantly speedup the execution.

2 Preliminaries

In this paper we consider only simple graphs without loops and multiple edges. We use the standard notations for graphs, son = |V(G)| andm = |E(G)|. ForagraphG = (V, E) and a pair of vertices i,j [member of] V, we denote G + (i,j) a graph G' = (V,E[union] {(i,j)}), and G - (i,j) a graph G' = (V, E \ {(i,j)}). A graph G = (V,E) with a vertex set V = {1,..., n} is an interval graph if there is a set of intervals I = {[I.sub.1], ...,[I.sub.n]} on the real line such that (i,j) [member of] E iff [I.sub.i] [intersection] [I.sub.j] = 0. The set I is called an interval representation of the graph G. For an interval graph G, we say that an edge (ij) [member of] E(G) is an interval edge if G - (i, j) is also an interval graph. A sequence S of length 2n is called a string representation if each element x [member of] {1,..., n} appears exactly two times in S. Note that a string representation S encodes an interval graph in a natural way. For every x [member of] {1,..., n} let first (x) denote the index of the first appearance of x in S, second(x) denote the second one, and x is represented by an interval [I.sub.x] = [first(x),second(x)].

2.1 PQ-trees

It is easy to notice that an interval graph can have many different interval representations. Lueker and Booth (1979) introduced a data structure, called a PQ-tree, which encodes all normalized interval representations of an interval graph. A PQ-tree is a rooted labeled plane tree composed of leaves and two kinds of internal nodes called P-nodes, and Q-nodes respectively. The left to right ordering of the leaves of a PQ-tree T is called the frontier of T. We say that T encodes an interval graph G, if each maximal clique of the graph G is stored in exactly one leaf of T, and each vertex v [member of] V(G) belongs to a consecutive sequence of cliques in the frontier of T. Having a PQ-tree T one can obtain another PQ-tree T' which is equivalent to T using the following two operations: arbitrarily permute the children of a P-node, or reverse the order of the children of a Q-node. The crucial property of a PQ-tree T is the fact that for every permutation [sigma] of maximal cliques of the graph G such that each vertex belongs to a consecutive sequence of cliques, there is a PQ-tree T' that is equivalent to T, and frontier of T< represents [sigma]. In other words, each normalized interval representation of the graph G is represented by some tree equivalent to T.

2.2 MPQ-trees

PQ-trees are quite a simple and easy to understand data structure representing interval graphs, but unfortunately they may occupy up to O([n.sup.2]) space. To reduce the space consumption, Korte and Mohring (1989) presented modified PQ-trees called MPQ-trees. In an MPQ-tree, we do not store maximal cliques in leaves, but we assign to each P-node and each child of a Q-node a set of vertices in such a way that vertices laying on a path from the root of the tree to some leaf represent a maximal clique in G, see Figure 1C for an example. For a Q-node Q with children [T.sub.1], ..., [T.sub.k], we denote Si the set of vertices assigned to [T.sub.i], and call it the i-th section of Q. Note that, each vertex belongs to the consecutive sequence of maximal cliques, so it has to belong to consecutive sequence of sections of a Q-node. Hence, in order to limit the used space, we can store the information about the vertex x only in the first and last section it belongs to. Thanks to this modification, an MPQ-tree is an O(n) space representation of an interval graph. In this paper we show several drawings of MPQ-trees. We represent P-nodes as circles, and Q-nodes as rectangles divided into smaller rectangles representing sections of the Q-node. For instance, in the Figure 1C the root is an empty P-node, and the vertex 6 belongs to the sections [S.sub.2] and [S.sub.3] of the only Q-node.

2.3 Known results

During past decades, many researchers published their results on constructing both PQ-trees and MPQ-trees. Those trees were mostly used to determine whether a given graph G = (V, E) is an interval graph or not. Lueker and Booth (1979) in their recognition algorithm used PQ-trees and proved that for a given graph G the corresponding PQ-tree can be computed in O(n + m) time. Korte and Mohring (1989) presented analogous result for MPQ-trees. In this paper we are most interested in work of T. Saitoh (2007) who presented an algorithm that constructs an MPQ-tree for a given interval graph representation and works in O(n log n) time, or O(n) if the endpoints of intervals are given in an ascending order.

Theorem 1 (T. Saitoh (2007) Thm.12) If the graph G is given as an interval representation such that the endpoints are sorted by the coordinates, then there is an algorithm that produces an MPQ-tree corresponding to G in O(n) time.

Clearly, having a string representation of the graph G, we can produce an interval representation satisfying the conditions of Theorem 1 in O(n) time. Hence, we have the following corollary.

Corollary 2 There is an algorithm that for a given string representation S of the graph G builds a corresponding MPQ-tree T in O(n) time.

Before we proceed to technical definitions and lemmas, we provide some naming conventions we are going to use in the rest of this paper. To avoid a confusion when talking about elements of a graph and elements of a tree, we always refer elements of a graph as vertices and elements of a tree as nodes. For a vertex v of a graph G, we denote node(v) the node of a corresponding MPQ-tree T such that v belongs to the set assigned to that node. For a node with k subtrees [T.sub.1],..., [T.sub.k], we denote [V.sub.i] the set of all vertices that are assigned to the nodes of a subtree [T.sub.i]. If [V.sub.i] = 0, then we say that a subtree [T.sub.i] is empty. For a Q-node we say that a vertex v has its left endpoint in a section [S.sub.l{v)], if v belongs to [S.sub.l{v)] and does not belong to any other section [S.sub.b] with b < l(v). Analogously, we say that v has its right endpoint in [S.sub.r{v)], if v belongs to [S.sub.r{v)] and does not belong to any other section [S.sub.b] with b > r(v). Vertex v is contained in sections [S.sub.a],..., [S.sub.b], if a [less than or equal to] l(v) < r(v) [less than or equal to] b.

For an MPQ-tree T we define a 2n-element string S called string representation of T. This string is built recursively over the structure of T. For a P-node we first output all vertices that belong to that node, then recursively string representations of the children from left to right, and at the end yet again all vertices that belong to that node, but now in the reversed order. Hence, the string representation for a P-node with vertices {1,..., k} and no children is 123 ... (k - 1)kk(k - 1)... 321. A string representation for a Q-node is a concatenation of string representations for its sections. The string for a section [S.sub.i] starts with vertices that have its left endpoint in [S.sub.i], then there is a string for a subtree [T.sub.i], and finally vertices that have its right endpoint in [S.sub.i]. It is easy to see that string representation of T is also a string representation of the graph corresponding to T. We also define a normalized string representation of T. Consider a permutation [sigma] : {1,..., n} [right arrow] {1,..., n}, and a string [sigma](S), which results from the application of [sigma] to each element of S. Normalized string representation is the lexicographically smallest string [sigma](S) among all permutations [sigma]. Finally, we recall some properties of MPQ-trees produced by the Algorithm from Theorem 1.

Lemma 3 (Korte and Mohring (1989); Uehara (2005)) In the MPQ-tree constructed in Theorem 1 for every Q-node with k children we have:

a) [V.sub.1] [not equal to] 0 and [V.sub.k] [not equal to] 0,

b) [S.sub.1] [subset] [S.sub.2] and [S.sub.k] [subset] [S.sub.k-1],

c) [S.sub.i-1] [intersection][S.sub.i][not equal to]0for2 [less than or equal to] i [less than or equal to] k,

d) [S.sub.i-1] [not equal to] [S.sub.i] for 2 [less than or equal to] i [less than or equal to] k,

e) ([S.sub.i] [intersection] [S.sub.i+1]) \ [S.sub.1] [not equal to] 0 and ([S.sub.i-1] [intersection] [S.sub.i]) \ [S.sub.k] = 0 for 2 [less than or equal to] i [less than or equal to] k - 1, and

f) ([S.sub.i-1] [union] [V.sub.i-1]) \ [S.sub.i] [not equal to] 0 and ([S.sub.i] [union] [V.sub.i]) \ [S.sub.i-1] [less than or equal to] 0 for 2 [less than or equal to] i [less than or equal to] k.

Moreover:

g) there are no two empty P-nodes such that one of them is a parent of the other,

h) there is no P-node that have only one child which root is also a P-node, and

i) P-nodes have no empty children

see Figure 2.

It is worth noting that MPQ-trees describe interval graph in a natural recursive way. If G consists of at least 2 connected components, then the root node of MPQ-tree T corresponding with G is an empty P-node, and each subtree corresponds to each connected component of G. If G is connected an vertices [v.sub.i1],..., [v.sub.ik] are universal in G (vertex is universal if it is connected to all other vertices), then the root of T node is a P-node containing [v.sub.i1],...,[v.sub.ik]. In the remaining cases the root of T is a Q-node.

3 Canonical MPQ-tree

In this section, we define a total ordering < on MPQ-trees. One may notice that the lexicographical order on string representations is a total ordering on MPQ-trees, but for complexity reasons we introduce a different one. Denote |T| the number of vertices contained in the tree T, c(T) the number of children of the root of T, and ex(T) the number of vertices that belong to the root of T. We assign a tuple [t.sub.T] = (|T|,ex(T), c(T)) [member of] [N.sup.3] to every tree T, and say that if [t.sub.T1] is lexicographically smaller than [t.sub.T2], then [T.sub.1]<[T.sub.2]. For two trees [T.sub.1] and [T.sub.2] such that [t.sub.T1] = [t.sub.T2], we say that [T.sub.1] < [T.sub.2], if the normalized string representation of [T.sub.1] is lexicographically not greater than normalized string representation of [T.sub.2]. We say that MPQ-tree T is in canonical form, if for every other tree T' representing the same graph G we have T < T'. A string S is a canonical string, if it is a normalized string representation of a canonical tree. Observe that if T is in a canonical form, then all subtrees of T are in a canonical form. Clearly, if some subtree of T is not in a canonical form, then we may rotate it and obtain a lexicographically smaller string.

Theorem 4 Two interval graphs G1 and [G.sub.2] are isomorphic if and only if their canonical strings [S.sub.1] and [S.sub.2] are equal.

Theorem 5 There is an algorithm that for every MPQ-tree T computes its canonical form in O(n log n) time.

Proof: At the very beginning, we shall compute a function g that for every vertex v will describe its relative position among all vertices from node(v). We compute this function for each P-node independently, and for all Q-nodes collectively. For a P-node with j vertices [z.sub.1], ..., [z.sub.j], we assign g([z.sub.i]) = i. Thus, we can compute the function g for all P-nodes in O(n) time. In order to compute this function for all Q-nodes, at first we assign a tuple (l(v),r(v)) to each vertex v which belongs to some Q-node. Then we sort all tuples using radix sort algorithm, and visit vertices in the order determined by their tuples. For each Q-node we keep a local counter that starts with 1 and increases each time we visit a vertex from this node. Thus, because all vertices are from the set {1,..., n}, and each Q-node has a linear in terms of n number of sections, we compute this function for all vertices in O(n) time.

We shall construct a function f that assigns an integer f(T') > n to every subtree T' of a tree T in such a way that [T.sub.1] < [T.sub.2] [left right arrow] f([T.sub.1]) < f([T.sub.2]). Simultaneously we will rotate subtrees so that they are in canonical form. At first, we compute tuples [t.sub.T], for each subtree T' of a tree T. Clearly, it can be easily done in O(n) time. Then, we sort the tuples lexicographically in O(n) using radix sort algorithm. In the next phases, we inspect nodes of tree T that have the same tuple (|T' |, ex (T'), c(T')), and we do it from the smallest tuples to the biggest ones. Observe that, when we define the value of the function f for T', the values for all subtrees of T' are already computed.

All subtrees of T' are in a canonical form, so in order to compute a canonical form of T', we need to determine the order of its children. If the root of T' is a P-node, then we use integers f([T.sub.i]) as keys for children, and sort them in O(c log c) time, where c = c(T'). If the root of T' is a Q-node Q, then we may leave it in the form it is or reverse it. To decide what to do, we compute a special string representation S*, which is similar to the string representation, but for each vertex v that belongs to Q we put g(v) instead of v, and instead of inserting the whole string for a subtree [T.sub.i] , we put a single number f([T.sub.i]). Hence, the produced string has length 2 * ex(T') + c(T') and is produced in time proportional to its length. We also produce similar string for a rotated node, and if that string is lexicographically smaller than the original one, then we rotate Q. Otherwise, we do nothing.

We have just computed canonical forms for all subtrees with the same tuple. For each of them we produce a special string, and sort those strings lexicographically. Finally, we assign values from the set {F + 1,F + 2,...}, where F is the maximal number assigned to trees with lexicographically smaller tuples (or F = n if there are no smaller). We assign those numbers according to the computed order giving the same value to the subtrees with the same special string representation, and that finishes the algorithm description.

Now, we prove the algorithm works in the declared time. As we mentioned before, the computation of the function g is linear in time. The same applies to the computation and sorting for the node tuples. Sorting children of a P-node with c children takes O(c log c). Hence, because all P-nodes cannot have more than O(n) children in total, we conclude that sorting children for all P-nodes takes no more than O(n log n) time. The length of a special string for a Q-node with j vertices and k sections is O(j + k). Thus, the total processing time for all Q-nodes is linear in terms of n.

The only thing we have not counted yet is the time spent on sorting subtrees with the same tuple. Note that for a tuple (s, e, c), each special string has length exactly 2e + c. Let [n.sub.sec] be the number of subtrees having a tuple (s, e, c). Sorting process for those subtrees takes no more than O((e + c)[n.sub.sec] [logn.sub.sec]). Thus, all sortings together take O([[SIGMA].sub.sec] (e + c)[n.sub.sec] [logn.sub.sec]). Note that [n.sub.sec] [less than or equal to] n, so we only need to show that [[SIGMA].sub.sec] (e + c)[n.sub.sec] is O(n). But, clearly [[SIGMA].sub.sec] [en.sub.sec] = n since this sum counts vertices in all nodes. Similarly, [[SIGMA].sub.sec] [cn.sub.sec] equals the number of edges in T, and we are done.

4 Interval edges

In this section we present a series of lemmas that characterize the interval edges for the interval graph G. Moreover, for each interval edge (x, y), we also present a linear in terms of n algorithm that produces a string representation for the interval graph G - (x, y). For an edge (x, y) that is not an interval edge, we prove the existence of an induced chordless cycle on four vertices or an asteroidal triple in G - (x, y). The characterization does not use the mere graph G, but the corresponding MPQ-tree T instead.

First, let us introduce an useful definition. We say that x is over y in T, if (x, y) [member of] E(G) and node(x) is the lowest common ancestor of node(x) and node(y) in T. Notice that, if there is an edge (x, y) in the graph G, then x is over y, or y is over x. Now, we make an easy observation on interval edges.

Observation 6 If there are at least two vertices [z.sub.1] and [z.sub.2] such that both x and y are over [z.sub.1] and [z.sub.2], and there is no edge ([z.sub.1], [z.sub.2]), then (x, y) is not an interval edge.

Proof: Vertices x,[z.sub.1],y and [z.sub.2] in that order form a cycle of length 4. We assumed that there is no edge between [z.sub.1] and [z.sub.2], so if there is no edge between x and y, then this cycle is chordless in G - (x, y), see Figure 3. Hence, G - (x, y) is not a chordal graph and so not an interval graph.

The above observation is useful when we want to prove that the edge (x, y) is not an interval edge. However, in cases when (x, y) is an interval edge, we want to show a linear time algorithm that produces a string representation for a graph G - (x, y). The following lemma, we call the swapping lemma, comes handy when we try to produce the mentioned string. It shows when we can swap two consecutive elements in a string representation without adding or removing any edges to the represented graph.

Lemma 7 Let S1 and [S.sub.2] be string representations, such that [S.sub.2] is created from S1 by swapping elements at positions i and i + 1 for some i. Denote a the element at the i-th position in S1, and b the element at the (i + 1)-th position ([S.sub.1] = ....ab.. and [S.sub.2] = ....ba..). S1 and S2 represent the same interval graph iff both elements at swapped positions represent either left endpoints or right endpoints.

Proof: Clearly, at most one edge can be added or removed by swapping those two elements. If we swap the left endpoint of a and the right endpoint of b, then we remove an edge (a, b). If we swap the right endpoint of a and the left endpoint of b, then we add an edge (a, b) which is not present in [S.sub.1]. If both elements represent left endpoints, then right endpoints for both a and b are to the right of i + 1, hence no edge is added or removed. Similar argument works when both elements represent right endpoints.

Our aim is to characterize all interval edges encoded by an MPQ-tree T. Hence, as an input we are given an MPQ-tree T and some edge (x, y) [member of] E(G). Without loss of generality, we assume that x is over y in T, and we work under this assumption in the following subsections. We split our argument into cases according to the relative position of node(x) and node(y) in T.

4.1 x and y belong to the same P-node

At first, we consider the case where both x and y belong to the same P-node P in T. We show that under this assumption, the edge (x, y) is an interval edge if and only if P is a leaf in T.

Lemma 8 Ifnode(x) = node(y) is a P-node that is not a leaf, then (x, y) is not an interval edge.

Proof: Let P be the considered common P-node, and assume it has j subtrees for some j [greater than or equal to] 1. If j [greater than or equal to] 2, then by Lemma 3i let [z.sub.1] [member of] [V.sub.1] and [z.sub.2][member of][V.sub.2]. Clearly, there is no edge between [z.sub.1] and [z.sub.2] and both x and y are over [z.sub.1] and [z.sub.2]. Hence, Observation 6 implies that (x, y) is not an interval edge. Thus, P has exactly one subtree, and according to Lemma 3h, its root has to be a Q-node, see Figure 4. Moreover, Lemma 3a implies, that the first and last sections of a Q-node have nonempty subtrees. Let [z.sub.1] belong to the first subtree, and [z.sub.2] belong to the last one. Yet again, conditions of the Observation 6 are satisfied, so (x, y) is not an interval edge.

Lemma 9 Ifnode(x) = node(y) is a P-node that is a leaf, then (x,y) is an interval edge. Moreover, there is a linear time algorithm that produces a string representation for the graph G - (x, y).

Proof: Without loss of generality assume that x < y, and consider the canonical string S for the MPQ-tree T. Clearly, S is of the form S = LAxByCCyBxAR, see Figure 5. In order to remove the edge (x, y) we find the first and the last occurrence of x in S. Then, until x does not occupy two consecutive positions, we swap S[i] with S[i + 1], and S[j] with S[j - 1], where i denotes the first occurrence of x and j denotes the second. Next, we do the same for y, and as a result we get a string such that both y's are next to each other and are surrounded by both x's, see Figure 5c. Finally, we swap the first occurrence of y with the second occurrence of x, effectively removing the edge (x, y). Clearly, this procedure runs in O(n) time, but we have to ensure that it does not add or remove any other edge. Note that, all modifications are performed in a substring of S that represents a clique, and is of the form [z.sub.1][z.sub.2]... [z.sub.k][z.sub.k] ... [z.sub.2][z.sub.1]. Hence, each swapping operation - except the last one - swapped either two left endpoints or two right endpoints. Thus, Lemma 7 ensures that no edge was added or removed during this process. Finally, during the last swap x and y occupy four consecutive indexes. Hence, the only affected vertices are x and y.

4.2 x and y belong to the same Q-node

The next case is when both vertices belong to the same Q-node. Here we show that (x, y) is an interval edge if and only if x and y have exactly one common section and the subtree of this section represents a clique (possibly empty).

Lemma 10 Ifnode(x) = node(y) is a Q-node, then (x, y) is not an interval edge if:

1. x andy have more than one common section in node(x) = node(y), or

2. a subtree of the common section does not represent a clique (possibly empty).

Proof: Assume that there is a common section Si and its nonempty subtree [T.sub.i] that does not represent a clique. Hence, there are at least two vertices [z.sub.1] and [z.sub.2] in Vi such that there is no edge between them, otherwise [T.sub.i] would represent a clique. Thus, Observation 6 implies that (x, y) is not an interval edge. Moreover, if there are two common sections [S.sub.i] and [S.sub.j] such that both of them have nonempty subtrees [T.sub.i] and [T.sub.j] respectively, then we may choose [z.sub.1] [member of] Vi and [z.sub.2] [member of] [V.sub.j] and use the same argument. This proves that common sections have empty subtrees except at most one which represents a clique. Now, assume that there is more than one common section ie. [S.sub.i], [S.sub.i+1], ..., [S.sub.j-1],[S.sub.j], and without loss of generality [S.sub.i] has an empty subtree. Lemma 3f implies that there is a vertex [z.sub.1] for which the section [S.sub.i] is the last one ([z.sub.1] does not belong to sections [S.sub.i+1],..., [S.sub.j]). Notice that [z.sub.1] [member of] {x, y}, otherwise j = i. If there is a nonempty subtree [T.sub.a] for some i < a [less than or equal to] j, then we choose [z.sub.2] [member of] [V.sub.a], and Observation 6 leads to an induced chordless cycle. Hence, all common subtrees are empty and Lemma 3f gives us a vertex [z.sub.2] for which [S.sub.j] is the first section. Observation 6 for vertices x, y, [z.sub.1] and [z.sub.2] finishes the proof.

Lemma 11 Ifnode(x) = node(y) is a Q-node, x and y have exactly one common section Si in it, and the subtree Ti represents a clique, then (x, y) is an interval edge. Moreover, there is a linear time algorithm that produces a string representation for the graph G - (x, y).

Proof: Again, we assume that x < y and consider the canonical string S for the MPQ-tree T, but in this case S has a more complex form than in theLemma9. In fact, itis of [theformP.sub.1][xP.sub.2][L.sub.1][yL.sub.2][V.sub.i][V.sub.i][R.sub.1][xR.sub.2][S.sub.1][yS.sub.2], where [L.sub.1] [union] [L.sub.2] represents the left endpoints of vertices from [S.sub.i], [R.sub.1] [union] [R.sub.2] represents the right endpoints of vertices from [S.sub.i], and Vi [union] represents a clique from the subtree, see Figure 6. In order to remove the edge (x, y), at first we need to determine for each element in S whether it represents the left or the right endpoint. It can be easily done in O(n), since all elements in S belong to the set {1,..., n}. The next phase swaps the first occurrence of y with its successor until the next element represents a right endpoint. Analogously, we swap the second occurrence of x with its predecessor until the next element represents a left endpoint. Clearly, because of Lemma 7 we did not add or remove any edge till this moment, and S looks like in Figure 6c. Finally, we can remove the edge (x, y) by swapping the first occurrence of y with the second occurrence of x, that in fact occupy consecutive positions in S.

4.3 x and y belong to different nodes.

In the previous two subsections, we provided a full classification for the cases where x and y belong to the same node in T. In this subsection, we consider the cases where x and y belong to different nodes in

T. Before we present our results in those cases, we introduce a terminology that allows us to describe a relative position of node(x) and node(y) in T.

For a Q-node with k sections S1,..., [S.sub.k], we say that the section [S.sub.a] is a central section if 1 < a < k. Sections [S.sub.1] and [S.sub.k] are called non-central sections. For a vertex v we say that the section [S.sub.a] is a v-central section if l(v) < a < r(v). Sections [Sl.sub.(v)] and [S.sub.r(v)] are v-non-central sections. For every two vertices x and y, there is exactly one path in the tree T between node(x) and node(y). We say that this unique path is an {x,y)-tree-pathifxisovery inT. For an (x,y)-tree-path: node(x) = [n.sub.1]-[n.sub.2]-.. .-[n.sub.t] = node(y), we say that this path goes through the central section if there is a Q-node ni for 1 < i < t such that [n.sub.i+1] belongs to a subtree of some central section of [n.sub.i], see Figure 10. Moreover, we say that the path starts in a central section if [n.sub.1] is a Q-node, and [n.sub.2] belongs to a subtree of some x-central section. Analogously, it starts in a non-central section if [n.sub.2] belongs to a subtree of some x-non-central section. We also say that an (x, y)-tree-path starts in a P-node, if node(x) is a P-node, and ends in a P-node if node(y) is a P-node. Analogous definitions apply to Q-nodes. Finally, we say that an (x, y)-tree-path is almost rotable if it does not go through the central section, and ends in a P-node that is a leaf. An (x, y) -tree-path is rotable if it is almost rotable, and either starts in a P-node, or starts in a non-central section. Intuitively, if an (x, y) -tree-path is almost rotable, then we are able to rotate all the nodes on the path [n.sub.2] - ... - [n.sub.t] in such a way that y is the leftmost vertex in the subtree which root is [n.sub.2].

Now we are ready to characterize interval edges in the case where x and y belong to different nodes in T. We prove that if (x, y)-tree-path is rotable, then (x, y) is an interval edge. Unfortunately, the reverse implication is not true and sometimes (x, y)-tree-path is not rotable, but (x, y) is still an interval edge. We shall prove that this happens only for almost rotable (x, y)-tree-paths satisfying some additional, and quite technical, conditions. First, we show how to compute a string representation for an interval graph G - (x, y) if (x, y)-tree-path is rotable.

Lemma 12 If an (x,y) -tree-path is rotable, then (x,y) is an interval edge. Moreover, there is a linear time algorithm that produces a string representation for the graph G - (x, y).

Proof: In order to remove the edge (x, y), we do not produce a canonical string S immediately. At first, we need to adjust the tree T using some preprocessing. If node(x) is a Q-node, then we rotate node(x) so that (x, y)-tree-path starts in the section [S.sub.l(x)]. Then, we rotate T so that the path from node(x) to node(y) goes through the leftmost children of P-nodes and the leftmost sections of Q-nodes. Let T be the result of the described adjustment, and let S be a string representation of T. Clearly, S is of form LxAByCCyBDxR, see Figure 7, and both occurrences of y lay in between occurrences of x in S. Node node(y) is a P-node that is a leaf, so we start with moving the first occurrence of y to the right and the second occurrence of y to the left until they both meet, as in the Lemma 9. All vertices that lay between the first occurrence of x and the first occurrence of y represent the left endpoints. Hence, we can swap the first occurrence of x with its successor until it meets the second occurrence of y. Lemma 7 ensures that no edge is added or removed during this process. Finally, moving x once more to the right swaps the left endpoint of x with the right endpoint of y effectively removing the edge (x, y).

Now, we consider those (x, y) -tree-paths that are not rotable, but are almost rotable. Hence, all those paths start in some x-central section of some Q-node. We denote [S.sub.1],..., [S.sub.k] the sections of considered Q-node, and [S.sub.a] the x-central section where the (x, y) -tree-path starts. As we already mentioned, sometimes in that case the edge (x, y) is an interval edge. The next two lemmas establish the required conditions for that to happen.

Lemma 13 If an (x, y) -tree-path is almost rotable, starts in a central section [S.sub.a], y has no neighbor in a subtree [T.sub.a] and:

1. [[there exists].sub.1<b[less than or equal to]l(x)] : [S.sub.a] \ {x} [subset] [S.sub.b] andSb-1 [intersection] [S.sub.b] [subset] [S.sub.a], or

2. [[there exists].sub.r](x)[less than or equal to]b<k : [S.sub.a] \ {x} [subset] [S.sub.b] [andS.sub.b] [intersection] [S.sub.b+1] [subset] [S.sub.a], or

3. [S.sub.a] \ {x} [subset] S1, or

4. [S.sub.a] \ {x} [subset] [S.sub.k],

then (x, y) is an interval edge. Moreover, there is a linear time algorithm that produces a string representation for the graph G - (x, y).

Proof: Proofs for all four cases are very similar, so we show only the proof for the first case. Assume that there is a 1 < b [less than or equal to] l(x) such that [S.sub.a] \ {x} [subset] [S.sub.b] and [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.a]. As in the proof of Lemma 12, before we produce the string representation S, we need to make some adjustments in the tree T. At first, we insert a new section S* =[S.sub.a]\ {x} in between sections [S.sub.b-1] and [S.sub.b], see Figure 8. Clearly, an insertion of a new section does not remove the old edges, but it might add some new ones. However, the section S* is a subset of an already existing section, so it is not the case. Moreover, the condition that each vertex belongs to the sequence of consecutive sections is preserved. That's because we assumed that [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.a] and [S.sub.a] \ {x} [subset] [S.sub.b]. Next, we remove the vertex y from the subtree [T.sub.a]. We also define a subtree T* of the section S* to be a single P-node containing y. Note that y has no neighbor in [T.sub.a], so no edges were removed, except the edge (x, y). Thus, we obtained a tree T' that encodes the graph G - (x, y). In order to get the string representation for the graph G - (x, y) it is enough to compute the string representation for T'. We proved only the first case, but observe that the second case is symmetric, and cases 3 and 4 are the corner cases, so in the third case we simply insert the section S* before [S.sub.1] and in the fourth case we insert S* after [S.sub.k].

Lemma 14 If an (x, y) -tree-path is almost rotable, starts in a central section [S.sub.a], y has a neighbor in a subtree [T.sub.a] and:

1. l(x) > 1 and [S.sub.a] \ {x} [subset] [S.sub.l(x)] and [S.sub.l(x)-1] [intersection] [S.sub.l(x)] [subset] [S.sub.a], or

2. r(x) < k [andS.sub.a] \ {x} [subset] [S.sub.r(x)] and [S.sub.r(x)] [intersection] [S.sub.r(x)+1] [subset] [S.sub.a], or

3. l(x) = 1 and [S.sub.a] \ {x} [subset] [S.sub.1], or

4. r(x) = k and [S.sub.a] \ {x} [subset] [S.sub.k],

then (x, y) is an interval edge. Moreover, there is a linear time algorithm that produces a string representation for the graph G - (x, y).

Proof: The proof of this lemma is similar to the proof of Lemma 13, but now y has at least one neighbor in [T.sub.a], so we cannot simply remove y from [T.sub.a]. That's also the reason why conditions of this lemma are more strict than in the previous one. Yet again, we are going to prove only the first case, so assume that [S.sub.a] \ {x} c [S.sub.l(x)] and [Sl.sub.(x)-1] n [S.sub.l(x)] c [S.sub.a]. Instead of inserting a new section, we remove the section [S.sub.a] and insert it in between sections [Sl.sub.(x)-1] and [S.sub.l(x)], see Figure 9. Clearly, no edge is added or removed, and the condition that each vertex belongs to the sequence of consecutive sections is preserved. Now, we remove x from the section [S.sub.a]. This, removes the edge (x, y), but also all the edges (x, v), where v [member of] [V.sub.a]. In the next phase, we are going to restore those edges. In order to do it, at first we rotate the subtree [T.sub.a] in such a way that the path from node(x) to node(y) goes through the leftmost children of P-nodes and the leftmost sections of Q-nodes. Then, we compute the string representation S of the modified tree, and move the first occurrence of y to the right and the second occurrence of y to the left until both meet, as in the Lemma 9. After this operation is done, y is the leftmost vertex of the tree [T.sub.a] - its right endpoint appears first in the string representation of [T.sub.a]. In order to restore all the removed edges except (x, y), we move the first occurrence of x in S to the left, until its predecessor is the second occurrence of y. Clearly, this procedure restores all the removed edges except (x,y).

The above two lemmas show the only cases where (x, y) -tree-path is not rotable, but (x, y) is an interval edge. Now, we are going to show that if (x, y) -tree-path is not rotable, and the conditions of those lemmas are not satisfied, then (x, y) is not an interval edge. At first, we prove that if (x, y)-tree-path does not end in a P-node that is a leaf, then (x, y) is not an interval edge.

Lemma 15 If an (x, y)-tree-path ends in a Q-node, then (x, y) is not an interval edge.

Proof: If y belongs only to central sections (y [member of] [S.sub.1] U [S.sub.k]), then Lemma 3f implies that there are vertices [z.sub.1] [member of] ([S.sub.l(y)] U [V.sub.l(y)]) \ [S.sub.l(y)+1] and [z.sub.2] [member of] ([S.sub.r(y)] U [V.sub.r(y)]) \ [S.sub.r(y)-1]. If y belongs to S1 (or [S.sub.k]), then just take [z.sub.1] [member of] [V.sub.1] (or [z.sub.2] [member of] [V.sub.k]). Clearly, there is no edge between [z.sub.1] and [z.sub.2], and both x and y are over [z.sub.1] and [z.sub.2]. Thus, Observation 6 finishes the proof.

Lemma 16 Ifan (x, y)-tree-path ends in a P-node that is not a leaf, then (x, y) is not an interval edge.

Proof: The same argument as in Lemma 8.

Now, we are going to prove that if an (x, y) -tree-path goes through the central section, then (x, y) is not an interval edge. First, we define a nested path. Consider a Q-node with k sections [S.sub.1], ..., [S.sub.k]. For a clarity let [S.sub.0] = [S.sub.k+1] = 0, and say that a set of vertices [P.sub.i,j] = ([S.sub.i][union]...[union][S.sub.j])\ ([S.sub.i-]1 [union] [S.sub.j+1]) is a nested path, if for every i [greater than or equal to] a < j there is at least one vertex [v.sub.a] [member of] [P.sub.i,j] that belongs to [S.sub.a] [intersection] [S.sub.a+1]. We call it a nested path, because vertices [v.sub.i], [v.sub.i+1]..., [v.sub.j-1] in that order form (possibly not simple) path in the graph G, and all of them are contained in the sections [S.sub.i],... ,[S.sub.j]. In the following lemma, we show that if (x, y)-tree-path goes through a central section of some Q-node, then we can find an asteroidal triple in the graph G - (x, y). Nested paths help us to find this triple.

Lemma 17 If (x, y)-tree-path goes through the central section, then (x, y) is not an interval edge.

Proof: Assume that the (x,y)-tree-path goes through some central section Si of a Q-node Q, and let [S.sub.1],..., [S.sub.k] be the sections of Q. Subtrees of the first and last section are nonempty, so let [z.sub.1] [member of] [V.sub.1] and [z.sub.2] [member of] [V.sub.k]. We show that vertices y, [z.sub.1] and [z.sub.2] form an asteroidal triple in the graph [member of] - (x, y).

There is no edge (x, y), so a path [z.sub.1] - x - [z.sub.2] avoids the neighborhood of y. To prove that there is a path between [z.sub.1] and y that avoids the neighborhood of [z.sub.2], we show that there is a nested path [P.sub.1,k-1], and so the shortest path of form [z.sub.1] - [P.sub.1,k-1] - y fulfill our requirements. Let [P.sub.1,j] be a nested path with maximum j < k. Clearly, such a path exists. Otherwise, either [S.sub.1] is empty, or all vertices that belong to [S.sub.1] belong to all sections. In both cases, properties listed in Lemma 3 are violated. Moreover, if j is less than k-1, then either [S.sub.j] [intersection] [S.sub.j+1] = 0, or [S.sub.j] [intersection] [S.sub.j+1] [subset] [S.sub.k]. Again, this contradicts Lemma 3, and we are done. A path from [z.sub.2] to y that avoids the neighborhood of [z.sub.1] is constructed in a similar way.

A consequence of the previous three lemmas is the following corollary.

Corollary 18 If an (x, y) -tree-path is not almost rotable, then (x, y) is not an interval edge.

We are almost done with the classification. In Lemma 12 we proved that if an (x, y) -tree-path is rotable, then (x, y) is always an interval edge. On the other hand, in Lemmas 15, 16 and 17 we considered (x, y)tree-paths that are not almost rotable, and showed that for such paths (x, y) is not an interval edge. Hence, the only remaining cases are the (x, y) -tree-paths that are almost rotable, but not rotable. In Lemmas 13 and 14 we investigated such paths, and proved that under some additional conditions (x, y) is an interval edge. Now we show that if an (x, y) -tree-path is almost rotable, but is not rotable, and conditions of Lemmas 13 and 14 are not satisfied, then (x, y) is not an interval edge. This case is the hardest one, and before we prove it, we need to prove two auxiliary lemmas.

Lemma 19 Let [S.sub.1],..., [S.sub.k] be the sections of some Q-node in an MPQ-tree T, and for the simplicity assume that [S.sub.0] = [S.sub.k+1] = 0. For every pair of indices (a, b) = (1, k), a < b there is a vertex v [member of] (([S.sub.a-1] [intersection] [S.sub.a]) \ [S.sub.b]) [union] (([S.sub.b] [intersection] [S.sub.b+1]) \ [S.sub.a]).

Proof: By contradiction, assume that for some pair of indices (a, b) there is no such vertex, so each vertex u [member of] [S.sub.a] U ... U [S.sub.b] is either contained in [S.sub.a],..., [S.sub.b], or belongs to [S.sub.a] [intersection] ... [intersection] [S.sub.b]. Without loss of generality assume that b < k. Each vertex belongs to at least two sections. Hence, no vertex has its right endpoint in [S.sub.a] or left endpoint in [S.sub.b], and Lemma 3 implies that [V.sub.a], [V.sub.b] and [V.sub.k] are not empty. Let [v.sub.a] [member of] [V.sub.a], [v.sub.b] [member of] [V.sub.b], [v.sub.k] [member of] [V.sub.k], and consider any maximal cliques [C.sub.a], [C.sub.b] and [C.sub.k] such that [v.sub.a] [member of] [C.sub.a], [v.sub.b] [member of] [C.sub.b] and [v.sub.k] [member of] [C.sub.k]. Note that, T encodes only those orderings of maximal cliques in which either [C.sub.a] < [C.sub.b] < [C.sub.k] or [C.sub.k] < [C.sub.b] < [C.sub.a]. Now, consider a modified tree T' in which we reverse the order of sections [S.sub.a],...,[S.sub.b]. Clearly, because of our assumptions, T' represents the same interval graph as T, but T' encodes an ordering [C.sub.b] < [C.sub.a] < [C.sub.k], which is not encoded by T. Thus, T is not a valid MPQ-tree, and we are done.

Lemma 20 If an (x,y) -tree-path starts in a central section [S.sub.a], andthere is a vertex q [member of] [S.sub.a]\([S.sub.l(x)] [union] [S.sub.r(x)]), then (x, y) is not an interval edge.

Proof: By contradiction, assume that (x, y) is an interval edge, Let [P.sub.l1,r1] for [r.sub.1] < a be a nested path that intersects q and have the smallest [l.sub.1]. Analogously, let [P.sub.l2,r2] for a < [l.sub.2] be a nested path that intersects q and have the biggest [r.sub.2]. Notice that these paths may not exist. For instance, if q has its right endpoint in [S.sub.a], then [P.sub.l2,r2] does not exist.

At first, we consider the case where both paths do not exist, and prove that there is an asteroidal triple in the graph G - (x, y). By Lemma 19, without loss of generality, there is a vertex v [member of] ([S.sub.r(q)] [intersection] [S.sub.r(q)+1]) \ [S.sub.l(q)]. Both paths do not exist, so v has to belong to [S.sub.a]. Moreover, Lemma 3f gives two vertices [v.sub.L] [intersection] ([S.sub.l(q)]U [V.sub.l(q)])\[S.sub.l(q)+1],and [v.sub.R ][intersection]([S.sub.r(q)+1 ]U [Vr.sub.(q)+1])\[S.sub.r(q)]. Thus, the paths: [v.sub.L]-x-[v.sub.R],[v.sub.L]-q-y, and [v.sub.R]-v-y certify the asteroidal triple {[v.sub.L], [v.sub.R], y}, and we are done in this case.

Now, assume that both paths exist, and put L = max {[l.sub.1], l(x)} and R = min {[r.sub.2], r(x)}. Lemma 3f implies that there is a vertex [v.sub.L] which has its right endpoint in [S.sub.L] or [v.sub.L] G [V.sub.L]. Analogously, define a vertex [v.sub.R] for the section [S.sub.R]. Clearly, both [v.sub.L] and [v.sub.R] are neighbors of x, but they do not belong to the neighborhood of q. Hence, {[v.sub.L], [v.sub.R], y} is an asteroidal triple in the graph G - (x, y). To see this, consider the paths: [v.sub.L]-x- [v.sub.R], [v.sub.L] - [P.sub.l1,r1] -q-y,[andv.sub.R]- [P.sub.l2,r2] -q-y. Thus, if both paths exist, then (x, y) is not an interval edge.

Without loss of generality, assume that [P.sub.l1,r1] exists, but [P.sub.l2,r2] does not. Lemma 19 implies that there is a vertex v such that v G ([S.sub.l1-1] [intersection] [S.sub.l1]) \ [S.sub.r(q)], or v G ([S.sub.r(q)] n [S.sub.r(q)+1]) \ [S.sub.l1]. Note that, a this point v and x might be the same vertex. We assumed that right path does not exist, so [S.sub.r(q)] [intersection] [S.sub.r(q)+1] c [S.sub.a]. Moreover, [l.sub.1] is the smallest index such that there is a nested path [P.sub.l1,r1] for [r.sub.1] < a that intersects q. Hence, [S.sub.l1-1] [intersection] [S.sub.l,1] C [S.sub.a], and so in both cases v belongs to [S.sub.a]. Lemma 3f gives three vertices: [v.sub.L] G ([Sl.sub.1] U [Vl.sub.1]) \ Sl1-1, [v.sub.R] [member of] (Sr(q) U [V.sub.r](q)) \ Sr(q)-1, and [v.sub.R]+1 [member of] (Sr(q)+1 U Vr(q)+1) \ [S.sub.r](q). Note that, both [v.sub.R] and [v.sub.R+1] are neighbors of x, and both [v.sub.L] and [v.sub.R+1] are not neighbors of q.

If [l.sub.1] < l(x), then the paths: [v.sub.L] - [P.sub.l1,r1] -x- [v.sub.R+1], [v.sub.L] - [P.sub.l1,r1] -q-y, and [v.sub.R+1] -x-q-y certify the asteroidal triple {[v.sub.L], [v.sub.R+1], y}.Thus, we conclude that l(x) [less than or equal to] [l.sub.1] < l(q), which means that the whole path [P.sub.l1,r1] is contained in x. Moreover, v and x are different vertices, and [v.sub.L] is a neighbor of x. If v G ([S.sub.l1]-1 [intersection] [S.sub.l1]) \ [S.sub.r(q)], then there is an asteroidal triple {[v.sub.L], [v.sub.R], y} certified by paths: [v.sub.L] - x - [v.sub.R], [v.sub.L] - v - y and [v.sub.R] - q - y. On the other hand, if v G ([S.sub.r(q)] [intersection] [S.sub.r(q)+1]) \ [S.sub.l1], then {[v.sub.L], [v.sub.R+1],y} is an asteroidal triple certified by paths: [v.sub.L] - x - [v.sub.R+1], [v.sub.L] - [P.sub.l1,r1] -q-y,and [v.sub.R+1] -v-y. Thus, in this case the edge (x, y) is also not an interval edge, and we are done.

Finally, we are ready to prove the last two negative results on interval edges.

Lemma 21 If an (x, y) -tree-path starts in a central section [S.sub.a], y has a neighbor in subtree [T.sub.a], and:

1. [mathematical expression not reproducible], and

2. [mathematical expression not reproducible], and

3. [mathematical expression not reproducible], and

4. [mathematical expression not reproducible],

where i = l(x) and j = r(x), then (x, y) is not an interval edge.

Proof: By contradiction, assume that (x, y) is an interval edge, and let z be the neighbor of y in [T.sub.a]. If both vertices [z.sub.i] and [z.sub.j] exist, and [z.sub.i] = [z.sub.j], then [z.sub.i] [member of] [S.sub.a] \ ([S.sub.i] U Sj), and Lemma 20 leads to a contradiction. Hence, if both of them exist, then [z.sub.i] = [z.sub.j]. But, in this case we can find an asteroidal triple {[v.sub.L], [v.sub.R], y}, where [v.sub.L] G (Si U Vi) \ [S.sub.i+1] and [v.sub.R] [member of] (Sj U [V.sub.j])\ [S.sub.j-1], certified by paths: [v.sub.L]-x- [v.sub.R], [v.sub.L] - [z.sub.j] - y, and [v.sub.R]-[z.sub.i]- y.

Thus, without loss of generality [z.sub.j] does not exist, and there is a vertex [z.sub.j] which belongs to ([S.sub.j ][intersection] [S.sub.j+1])\ [S.sub.a]. If zi also exists, then consider vertices [v.sub.L] [member of] ([S.sub.i-1] U [V.sub.i-1]) \ [S.sub.i], and [v.sub.R] G (Sj+1 U [V.sub.j+1]) \ [S.sub.j] that are given by Lemma 3f, and notice that paths: [v.sub.L] - [z.sub.i] - x - [z.sub.j] - [v.sub.R], [v.sub.L] - [z.sub.i] - x - z - y, and [v.sub.R]-[z.sub.j]-x-z-y certify the asteroidal triple {[v.sub.L], [v.sub.R],y}.

Hence, [z.sub.i] does not exist, and the only remaining case is where zj and [z.sub.i] exist. Note that if [z.sub.i] does not belong to Sj, then [z.sub.i ][member of] [S.sub.a]\ ([S.sub.i] U [S.sub.j]) and Lemma 20 gives a contradiction. Hence, [z.sub.i] [member of] [S.sub.j] and there is an edge between zi and [z.sub.j]. Lemma 3f gives vertices [v.sub.L] [member of] (Si U [V.sub.i])\[S.sub.i+1] and [v.sub.R] [member of] ([S.sub.j+1] U [V.sub.j+1])\[S.sub.j], and the asteroidal triple {[v.sub.L], [v.sub.R], y} is certified by paths: [v.sub.L]-x-[z.sub.j]-[v.sub.R], [v.sub.L]-x-z-y, and [v.sub.R]-zj-zi-y.

Lemma 22 If an (x, y)-tree-path starts in a central section [S.sub.a], y does not have a neighbor in subtree [T.sub.a], and:

1. [mathematical expression not reproducible] and

2. [mathematical expression not reproducible] and

3. [mathematical expression not reproducible] and

4. [mathematical expression not reproducible],

then (x, y) is not an interval edge.

Proof: By contradiction, assume that (x, y) is an interval edge. Let [p.sub.L] be the longest sequence [mathematical expression not reproducible], and [p.sub.R] be the longest sequence [mathematical expression not reproducible]. If both sequences are empty, then there are vertices [z.sub.l(x)] [member of] [S.sub.a] \ [S.sub.l(x)] and [z.sub.r(x)] [member of] [S.sub.a] \ [S.sub.r(x)]. But, the same argument as in Lemma 21, shows that there is an asteroidal triple in the graph G - (x, y). Thus, without loss of generality [p.sub.L] is not empty. If both sequences are not empty, then Lemma 3f gives vertices [v.sub.L] G ([S.sub.L-1] U [V.sub.L-1]) \ [S.sub.L] and [v.sub.R] [member of] ([S.sub.R+]1 U [V.sub.R+1]) \ [S.sub.R]. Moreover, both sequences are the longest possible, so there are vertices zL-1 [member of] [S.sub.a]\[S.sub.L-1] and [z.sub.R+1] [member of] [S.sub.a]\[S.sub.R+1].Thus,[thepathsv.sub.L]-[p.sub.L]-x-[p.sub.R]-[v.sub.R],[v.sub.L]-[p.sub.L]-x-[z.sub.R+1]-y, and [v.sub.R</SUB> - [p.sub.R] - x - [z.sub.L.sup.-1] - y certify the asteroidal triple {[v.sub.L]], [v.sub.R], y}. Hence, [p.sub.R] is empty, but [p.sub.L] is not. In that case, let [v.sub.R] be a vertex that belongs to [S.sub.r(x)] U [V.sub.r(x)], but does not belong to [S.sub.r(x)-1]. Sequence [p.sub.R] is empty, so there is a vertex [z.sub.l(x)] that belongs to [S.sub.a], but does not belong to [S.sub.r(x)]. Yet, again we can find an asteroidal triple {[v.sub.L], [v.sub.R], y} certified by paths: [v.sub.L] - [p.sub.L] - x - [v.sub.R], [v.sub.L] - [p.sub.L] - x - [z.sub.r(x)] - y, and [v.sub.R]-x-[z.sub.L-1]-y.

Finally, we are done with the classification of interval edges. For each edge (x, y) which is an interval edge, we provided a linear time algorithm that produces a string representation for the graph G - (x, y), see Lemmas 9,11,12,13, and 14. Moreover, for every edge (x, y) that is not an interval edge we presented structures certifying that G - (x, y) is not an interval graph, see Lemmas 8, 10,15, 16,17,21 and 22. The consequence of all those lemmas is the following theorem.

Theorem 23 There is a linear time algorithm, that for every MPQ-tree T representing graph G, and every interval edge (x, y), produces a string representation S' for the graph G - (x, y).

5 Listing interval edges

In this section we present an efficient algorithm that for a given MPQ-tree T lists all interval edges of the graph represented by T. Let [S.sub.1],..., [S.sub.k] be the sections of a Q-node Q. For b [member of] {2,..., k}, denote [f.sub.r](b) the maximal index of a section such that [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.fr(b)]. Analogously, for b [member of] {1,..., k - 1}, denote [f.sub.l](b) the minimal index of a section such that [S.sub.b] [intersection] [S.sub.b]+1 [subset] [S.sub.fi(b)]. For every vertex x which belongs to Q, and every l(x) [less than or equal to] a [less than or equal to] r(x) let:

[mathematical expression not reproducible]

In other words, if [S.sub.a] = {x}, then L*(x, a) = i if Si is the rightmost section such that there is a vertex v = x which belongs to [S.sub.a] and v has its left endpoint in Si. Now, we are ready to express the inclusion conditions on Q-node sections in terms of the functions [f.sub.l], [f.sub.r], L*, and R*.

Observation 24 In respect to the above definitions, we have the following equivalences:

1. [mathematical expression not reproducible]

2. [mathematical expression not reproducible]

3. [mathematical expression not reproducible]

Using those equivalences, we are able to reformulate the conditions of Lemmas 13 and 14.

Observation 25 For an (x, y) -tree-path that starts in a central section [S.sub.a], the conditions (1), (2), (3), and (4) of Lemma 13 are equivalent to the following:

1. L*(x,a) [less than or equal to] l(x) and min {l(x),R*(x, a)} > 1 and [f.sub.r](min {l(x),R*(x,a)}) > a, or

2. R*(x,a) [greater than or equal to] r(x)andmax{r(x),L*(x,a)}<[kandf.sub.l](max{r(x),L*(x,a)}) [less than or equal to] a,or

3. L*(x,a) = 1,or

4. R*(x,a) = k.

Proof: Note that, conditions (3) and (4) translate directly, and conditions (1) and (2) are symmetrical. Hence, we only show the equivalence of the first cases. At first, we show that if there is 1 < b [less than or equal to] l(x) such that [S.sub.a] \ {x} [subset] [S.sub.b] and [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.a], then L*(x, a) [less than or equal to] l(x) and [f.sub.r](min {l(x),R*(x, a)}) [greater than or equal to] a. From Observation 24 we have b [member of] [L*(x, a), R*(x, a)] and [f.sub.r](b) [greater than or equal to] a. Thus, L*(x,a) [less than or equal to] l(x), and 1 < b [less than or equal to] min{l(x),R*(x,a)}. Note that [f.sub.r] is a non-decreasing function, so [f.sub.r](b) [greater than or equal to] a, implies [f.sub.r](min{l(x),R*(x,a)}) [greater than or equal to] a, and we are done.

Now, we take b = min {l(x), R*(x, a)}, and show that if b > 1, [f.sub.r](b) [greater than or equal to] a, and L*(x,a) [less than or equal to] l(x), then [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.a] and [S.sub.a] \ {x} [subset] [S.sub.b]. Clearly, 1 < b [less than or equal to] l(x) and [f.sub.r](b) > a, so [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.a]. Hence, the only thing we need to show is [S.sub.a] \ {x} [subset] [S.sub.b]. According to Observation 24 it is equivalent to b [member of] [L*(x, a),R*(x, a)]. It is easy to see that for every x and a we have L*(x, a) [less than or equal to] R*(x, a). Thus, the interval [L*(x, a),R*(x, a)] is never empty. If b = R*(x, a), then we are done, so assume that b = l(x). But, in this case L* (x, a) [less than or equal to] l(x) = b [less than or equal to] R* (x, a), and we are done too.

A very similar proof applies to the following observation, so we leave it to the reader.

Observation 26 For an (x, y) -tree-path that starts in a central section [S.sub.a], the conditions (1), (2), (3), and (4) of Lemma 14 are equivalent to the following:

1. l(x) > 1andl(x) [member of] [L*(x,a),R*(x,a)] and [f.sub.r](l(x)) > a, or

2. r(x) <kandr(x) [member of] [L*(x, a), R*(x, a)] and [f.sub.l](r(x)) < a, or

3. l(x) = 1 and L*(x,a) = 1,or

4. r(x) = k and R*(x,a) = k.

Observations 25 and 26 provide fast and easy tests under the assumption that all the functions l, r, [f.sub.l], [f.sub.r], L* and R* are already computed. To represent functions l, r, [f.sub.l] and [f.sub.r] in computer's memory we use O(n)-element arrays of integers. Functions L* and R* in their explicit forms may require O([n.sup.2]) space. Hence, for performance purposes, we do not represent those functions as two-dimensional arrays. Instead, we observe that the function L* can be defined using some one-dimensional functions [L.sub.1] and [L.sub.2]. We set [L.sub.1](a) = max{l(v) : v [member of] [S.sub.a]}, and denote [v.sub.1](a) a vertex for which l([v.sub.1](a)) = L1(a). We also define [L.sub.2](a) = max{l(v) :v [member of] [S.sub.a]\ {v1(a)}}, or [L.sub.2](a) = 1 if [S.sub.a] = {[v.sub.1](a)}. Using those two functions we are able to compute the function L* in the following way:

[mathematical expression not reproducible]

Analogously, we can represent the function R* using two functions [R.sub.1] and [R.sub.2]. Now we are ready to show the interval edges enumeration algorithm.

Lemma 27 Functions l, r, [f.sub.l] and [f.sub.r] for all Q-nodes of the tree T can be computed in O(n log n) time.

Proof: We compute these functions for each Q-node separately. Assume that we are computing the function [f.sub.r] for a Q-node [Q.sub.d]. Let i be the minimum index of the section containing a right endpoint of some vertex from [S.sub.b-1] [intersection] [S.sub.b]. Clearly, [S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.i] and ([S.sub.b-1] [intersection] [S.sub.b] [subset] [S.sub.i+1]). Hence, [f.sub.r](b) = i, and in order to compute the function [f.sub.r] for all b, it is enough to scan the sections of [Q.sub.d] from left to right maintaining a heap of right endpoints. When algorithm enters the section [S.sub.b+1] it adds to the heap all right endpoints of vertices that have its left endpoint in [S.sub.b], assigns [f.sub.r] (b) to be the minimum value stored in the heap, and removes all the endpoints of vertices that have its right endpoint in [S.sub.b]. Thus, the computation of the function [f.sub.r] for [Q.sub.d] takes O([n.sub.d] log [n.sub.d]) time, where [n.sub.d] denotes the number of vertices in [Q.sub.d]. As [SIGMA][n.sub.d] [less than or equal to] n, the computation of all functions [f.sub.r] takes no more than O(n log n) time. A similar argument applies to the functions [f.sub.l].

Lemma 28 Functions L1, [L.sub.2], [R.sub.1] and [R.sub.2] for all Q-nodes of the tree T can be computed in O(n log n) time.

Proof: The proof is very similar to the proof of Lemma 27. Yet again, we use a heap of right or left endpoints, but now we are not only interested in the minimal element but also in the second one.

Theorem 29 There is an algorithm that for a given MPQ-tree T lists all its interval edges in O(max{n + m,nlogn}) time.

Proof: The algorithm is pretty straightforward. At first, we compute all the functions l, r, [f.sub.l], [f.sub.r], [L.sub.1], [L.sub.2], [R.sub.1] and [R.sub.2]. Then, we inspect all P-nodes and all sections of Q-nodes listing all edges (x, y) that satisfy the conditions of Lemmas 9 or 11. For a P-node that is a leaf, we list all pairs ([v.sub.a], [v.sub.b]) for a = b, while for the section [S.sub.i] with subtree that is either empty or is a P-node with no children, we list the edges of the form ([v.sub.L], [v.sub.R]), where [v.sub.L] is a vertex that has its right endpoint in [S.sub.i], and [v.sub.R] is a vertex that has its left endpoint in [S.sub.i]. Note that, an MPQ-tree has no more than O(n) nodes and sections. Moreover, we have a constant time access to all vertices [v.sub.L] and [v.sub.R]. Thus, this phase works in O(n + m).

Now, we want to find all interval edges (x, y) such that x and y belong to different nodes in T, and x is over y. Lemmas 15 and 16 imply that it is enough to consider only those pair of vertices (x, y), where y belongs to a leaf of T. Hence, for each leaf L of a tree T, we traverse a unique path between L and the root of T, starting from L, and listing edges of the form (x, y), where x belongs to the currently visited node, and y belongs to L. We do not list all such edges, but for each candidate we need to decide whether (x, y) is an interval edge or not. In order to do it efficiently, we keep two boolean variables: 1. does y have a neighbor in the visited subtree, and 2. does the path go through some central section. Using those two variables and precomputed functions, we can decide whether (x, y) is an interval edge in a constant time thanks to Lemma 12, and Observations 25 and 26. Thus, the time spent by the algorithm in this phase is bounded from above by the sum of lengths of all paths we have visited plus the number of tested edges. Lemma 3g, implies that on those paths there are no two consecutive empty P-nodes, so we can bound the sum of lengths of those paths by O(m). Thus, the time spent by the algorithm in this phase is O(n + m), and the whole algorithm works in O(max {n + m,n log n}) time.

6 Parent-Child Relationship

In this section we present the graph enumeration algorithm. We define a parent-child relationship in the same way as authors in Yamazaki et al. (2019) did using the following lemma.

Lemma 30 (Kiyomi et al. (2006)) IfG = (V, E) is an interval graph which is not a clique, then there is at least one edge e [member of] E such that G + e is also an interval graph.

Theorem 31 (Yamazaki et al. (2019) Thm. 5) Let G = (V, E) be any interval graph. Then its parent can be computed in O(n + m) time.

Yamazaki et al. used Lemma 30 and defined the parent of G to be a graph G + e such that G + e is an interval graph and e is lexicographically the smallest possible. They proved that for every interval graph G its parent can be computed in O(n + m) time - see Theorem 31. Thanks to the fact that we work with MPQ-trees and string representations, we are able to get rid of the O(m) factor using the algorithm from Theorem 1.

Theorem 32 There is a linear time algorithm that for every canonical MPQ-tree T representing an interval graph G that is not a clique, produces a string representation S' of a graph G + e, where e is the lexicographically smallest edge.

Proof: Let S be the canonical string forT. Let 12...j be the longest prefix of S such that j... 21 is asuffix of S. Clearly, such prefix can be found in O(n) time. Moreover, all vertices 1,..., j have degree n - 1 in the graph G. Hence there is no pair (x, y) [member of] E such that x [member of] {1,... , j}. We prove that there is a pair (j + 1, y) for some y [greater than or equal to] j + 2 such that G + (j + 1, y) is an interval graph. Let y be the leftmost endpoint of an interval that is to the right of the right endpoint of j + 1. If such y does not exist, then to the right of the right endpoint of j + 1 there are only right endpoints. Hence, G is a clique and we reached a contradiction. Thus, y exists, (j + 1, k) is an edge for all k [less than or equal to] y, and there is no edge between j + 1 and y. So, G + (j + 1, y) is the parent of G. In order to produce a string representation for the graph G + (j + 1, y), we move the right endpoint of j + 1 to the right until it passes the left endpoint of y. Lemma 7 guarantees that no edge except (j + 1, y) was added.

Finally, we take all the pieces together and present our main result.

Theorem 33 Let T be a canonical MPQ-tree representing a non-empty (m [greater than or equal to] 1) interval graph G. The set of canonical trees for children ofG in the family tree [F.sub.n] can be computed in O(nm log n) time.

Proof: At first, we list all interval edges for the tree T in O(max {n + m,nlogn}) time, see Theorem 29. Then, for each interval edge e, we produce a string representation S' of G - e in linear time, build MPQ-tree T for the interval graph represented by S' in O(n), and finally compute the canonical form of T' in O(n logn) time, see Theorems 23, 1, and 5. Hence, we compute all canonical strings for children candidates in O(nm log n) time. Theorem 4 implies that in order to check isomorphism, it is enough to remove duplicates from this set. It can be easily done by storing all computed strings in a trie. Finally, we need to filter out those graphs for which G is not a parent. For each candidate canonical string, we compute its parent string in O(n) time, see Theorem 32, build a canonical MPQ-tree in O(n log n) time and check whether its canonical string equals with a canonical string for the graph G in O(n) time. Thus, we filter out non-children in O(nm log n) time, and the whole process takes O(nm log n) time.

7 Performance

In the previous section we presented theoretical analysis of our enumeration algorithm. In this section we present two lemmas, that helped us to significantly speedup the execution of the algorithm. Unfortunately, presented tricks do not improve the worst-case time delay, and it is quite easy to show an MPQ-tree that even with those tricks take O(nm log n) time to process. We leave it as an exercise.

Lemma 34 Let [v.sub.1] [not equal to] [v.sub.2] be two vertices of the graph G = (V, E). If N([v.sub.1]) \ {[v.sub.2]} = N([v.sub.2]) \ {[v.sub.1]}, then for every y [member of] {[v.sub.1], [v.sub.2]} graphs G - ([v.sub.1], y) and G - ([v.sub.2], y) are isomorphic.

Proof: One can easily check that the function f : V [right arrow] V such that f([v.sub.1]) = [v.sub.2], f([v.sub.2]) = [v.sub.1] and f identifies other vertices, encodes an isomorphism between G - ([v.sub.1], y) and G - ([v.sub.2], y).

A consequence of the above lemma is the fact that if a P-node contains more than one vertex namely [v.sub.1],..., [v.sub.j], then graphs G - ([v.sub.1], y) and G - ([v.sub.a], y) for every a > 1 are isomorphic. Thus, when listing potential candidates for the children of the graph G, we may omit all edges of the form ([v.sub.a], y) for a > 1 and list only the edges of the form ([v.sub.1], y). The same argument applies to a Q-node and vertices that belong to the same sections.

Lemma 35 Let [v.sub.1],..., [v.sub.k] be a subset of vertices of the graph G = (V, E) such that [[for all].sub.i[not equal to]j] : N(vi) \ {[v.sub.j]} = N([v.sub.j]) \ {[v.sub.i]}, and [v.sub.1],..., [v.sub.k] form a clique in G. All graphs [G.sub.i,j] = G - ([v.sub.i], [v.sub.j]) are pairwise isomorphic.

Proof: Consider two graphs [G.sub.i,j] and [G.sub.i,j] and a function f : V [right arrow] V such thatf ([v.sub.i]) = [v.sub.i],, f([v.sub.j]) = [v.sub.j]. For the other verticesfis an identity.

A consequence of this lemma is the fact that if a P-node contains more than 2 vertices, then we may omit all the edges between them, except ([v.sub.1], [v.sub.2]). The same applies to the vertices that occupy the same sections of a Q-node. Both presented optimizations do not improve the worst case complexity of our algorithm, but significantly speed it up.

We implemented the proposed algorithms, and generated all non-isomorphic interval graphs on n vertices for all n [member of] {1,..., 15}. The results are available at https : //patrykmikos.staff.tcs.uj.edu.pl/graphs/.

References

H. Acan. Counting unlabeled interval graphs, 2018.

D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1):21-46, 1996. ISSN 0166-218X. doi: https://doi.org/10.1016/0166-218X(95)00026-N. First International Colloquium on Graphs and Optimization.

P. Hanlon. Counting interval graphs. Transactions ofThe American Mathematical Society - TRANS AMER MATHSOC, 272, 1982. doi: 10.2307/1998705.

N. P. J.C. Yang. On the enumeration of interval graphs. Proceedings of the American Mathematical Society Series B, 4:1-3,2017. ISSN 2330-1511. doi: https://doi.org/10.1090/bproc/27.

M. Kiyomi, S. Kijima, and T. Uno. Listing chordal graphs and interval graphs. In Graph-Theoretic Concepts in Computer Science, pages 68-77, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.

N. Korte and R. Mohring. An incremental linear-time algorithm for recognizing interval graphs. SIAM Journal on Computing, 18(1):68-81,1989. doi: 10.1137/0218005.

G. Lueker and K. Booth. A linear time algorithm for deciding interval graph isomorphism. J. ACM, 26 (2):183-195,1979. ISSN 0004-5411. doi: 10.1145/322123.322125.

R. McConnell and F. de Montgolfier. Algebraic operations on pq trees and modular decomposition trees. In D. Kratsch, editor, Graph-Theoretic Concepts in Computer Science, pages 421-432, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

T. Saitoh, K. Yamanaka, M. Kiyomi, and R. Uehara. Random generation and enumeration of proper interval graphs. IEICE Transactions on Information and Systems, E93.D(7): 1816-1823, 2010. doi: 10.1587/transinf.E93.D.1816.

T. Saitoh, Y. Otachi, K. Yamanaka, and R. Uehara. Random generation and enumeration of bipartite permutation graphs. Journal of Discrete Algorithms, 10:84-97,2012. ISSN 1570-8667. doi: https://doi.org/10.1016/j.jda.2011.11.001.

R. U. T. Saitoh, M. Kiyomi. Simple efficient algorithm for mpq-tree of an interval graph. IEICE Technical Report, 107(127):49-54,2007. ISSN 0913-5685.

R. Uehara. Canonical data structure for interval probe graphs. In R. Fleischer and G. Trippen, editors, Algorithms and Computation, pages 859-870, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.

K. Yamazaki, T. Saitoh, M. Kiyomi, and R. Uehara. Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs. In WALCOM: Algorithms and Computation, pages 8-19, Cham, 2018. Springer International Publishing.

K. Yamazaki, T. Saitoh, M. Kiyomi, and R. Uehara. Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs. Theoretical Computer Science, 2019. ISSN 0304-3975. doi: https://doi.org/10.1016/j.tcs.2019.04.017.

Patryk Mikos (*)

Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland

received 27th Feb. 2020, revised 15th Sep. 2020, accepted 23rd Dec. 2020.

(*) Research was partially supported by the National Science Center of Poland under grant no. 2014/14/A/ST6/00138.
COPYRIGHT 2021 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2021 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mikos, Patryk
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:4EXPO
Date:Jan 1, 2021
Words:12330
Previous Article:Wiener Index and Remoteness in Triangulations and Quadrangulations.
Next Article:Exponential multivalued forbidden configurations.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |