Scribd
Upload
66 views110 pages

Advanced Graph Algorithms

Uploaded by

arindamsinharay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
66 views110 pages

Advanced Graph Algorithms

Uploaded by

arindamsinharay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Google This book is provided in digital form with the permission of the rightsholder as part of a Google project to make the world's books discoverable online. The rightsholder has graciously given you the freedom to download all pages of this book. No additional commercial or other uses have been granted Please note that all copyrights remain reserved About Google Books Google's mission is to organize the world’s information and to make it universally accessible and useful. Google Books helps readers discover the world’s books while helping authors and publishers reach new audiences. You can search through the full text of this book on the web at ittp//[Link].com4 T. Kloks Advanced Graph Algorithms February 3, 2012 viizessy Google Contents 1 Exponential Algorithms Ll Independent set .. 1.2 Chromatic number 1.2.1 Three-coloring - 1.3. Domatic partition . 1.4 The traveling salesman problem LS Set cover - 1.6 Dominating set... 17 Subset sum ...... 18 Problems ......... 2 Graph Classes .. w 21 Perfect graphs 20 22 Cographs... : 23 22.1 Cotrees .... 225 2.2.2 Finding cliques in cographs . 225 2.3. Distance-hereditary graphs... 26 2.3.1. Decomposition trees for DH-graphs 228 2.3.2, Fedback vertex set in D-graphs 229 2.4 Chordal graphs. ; ; 231 2.4.1. Clique trees. 235 2.4.2 Algorithms for independent set, clique and vertex coloring in chordal graphs . 2.5 Interval graphs 2.6 Permutation graphs ae Waccinessad independent sets in permutation graphs 27 Problems . 9 Fiked-parameterAlgorithns 49 Bul Vertex cover ...... +52 3.2. Akernel for vertex cover +55 VE Contents 3.3. A better search-tree algorithm for vertex cover......2.2.2.+++ 58 34. Minimum fill-in + 60 3.5. Homogeneous coloring of perfect graphs + 68 3.6 Problems cteeseceetees * 65 4 Decomposition Trees . - 69 4.1 Graph minors ...... +69 4.2. Parameterized feedback vertex set 74 43. Treewidth . 275 4.3.1 An algorithm for treewidth two. 79 43.2 \Trees SOE a1 43.3. An O(n!*2) algorithm for treewidth... 82 4.3.4 Maximum clique in graphs of bounded treewidth... 85 435 Chromic number for graphs of bounded treewidth... 86 4.4 Rankwidth.. = beeeee 45. Monadic second-order logic 4.6 Problems References .. Index 1 Exponential Algorithms Let's face it: lots of interesting problems on graphs are NP-complete. In this chapter we have a look at exponential algorithms. Let's look at an example. Suppose we want to solve the maximum indepen- dent set problem on some graph G = (V,E). An independent set is a subset M C Vof vertices such that no two vertices in M are adjacent, The maximum independent set problem asks for an independent set M in G such that [MI is, maximal. An answer to the problem is called a ‘maximum’ independent set. We denote the cardinality of a maximum independent set in G with a{G) ‘An easy way to solve the problem is as follows. First, make a list of all sub- sets of vertices. Next, check which subsets are independent sets. Then count the number of vertices in each independent set and take the largest one. What is the time-complexity of this algorithm? Let n be the number of vertices in the graph G. Obviously, there are 2" subsets of vertices. Let M be a subset. We need to check if M is an independent set. We assume that the graph G is represented by an adjacency matrix A. Then we can check if two vertices are adjacent in constant time. Since M has O(n2) pairs we can check if M is an independent set in O(n®) time. Thus our algorithm runs in (O{n2-2) time. In the next section we show that we can do better. When we are dealing with exponential algorithm we don't care so much about the polynomial factors in the time-bound. The O* notation neglects the polynomial factors. So instead of O(n? - 2") we write O*(2"). ‘The O*-notation is pretty useful. For example, suppose our graph G is represented by adjacency lists. That is, for each vertex x in G there is a linked list L{x) of its neighbors. Now, to check if two vertices x and y are adjacent we need to check if y appears in the list L(x) or not. In the worst case L(x) contains n—1 vertices, so checking if y is inthis ist takes more than constant 2 1 Exponential Algorithms time. (Of course, we can construct the adjacency matrix A in O(n?) time and. then proceed as before.) If we use the O*-notation then we don’t need to worry about such details. Let p(n) be some polynomial, for example p(n) = 10 - n°. Suppose we can check if any subset M is an independent set in at most p(n) time. Then the algorithm described above runs in O(p(n) 2") = 0*(2) time. 1.1 Independent set ‘An independent set M in a graph G = (V,E) is maximal if any vertex in V\ M has at least one neighbor in M. Moon and Moser! have shown that, any graph with n vertices has at most 3"? maximal independent sets. Notice that a graph which is the union of © triangles achieves this bound. ‘There are algorithms that list all the maximal independent sets with poly- nomial delay. That means that there exists some polynomial p(n) such that the algorithm spends at most p(n) time before it generates the next (or the first) independent set. For example, the algorithm of Tsukiyama, et al, takes O{nm) time per maximal independent set, where n and m are the num- ber of vertices and edges in the graph.? These two results yield the following theorem. ‘Theorem 1.1, There exists an O*(1.4422") algorithm that solves the maximum independent set problem on a graph G, where n is the number of vertices in G. Proof. We use an algorithm which lists all maximal independent sets in G in Ofp(n} -3"”9) time for some polynomial p(n). Notice that Ofpin) -3"/) = 07/3") 0*(1.4422"), This proves the theorem, 0 Of course, this algorithm is much better than the O*(2") algorithm that we started with. In the rest ofthis section we show that we can still do a little bit better. *4. W. Moon and L, Moser, On cliques in graphs, Israel Journal of Mathematics 3 (1965), pp. 23-28, 2s, Tsukiyama, M. Ide, H. Ariyoshi and I Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM Journal on Computing 6 (1977), pp. S0S— 517. 1.1 Independent set 3 Let x be a vertex of G. As usual we use the notation N(x) for the set of, neighbors of a vertex x. The degree of x is |N(x]|. We also use the notation Nix for the closed neighborhood of x, which is Nix] = N(x) Ufx). Let x be a vertex in G. There are two types of independent sets, namely those that contain x and those that do not contain x. Consider a maximum independent set M. The next two lemmas show how to reduce the graph in teach of the two cases. Lemma 1.2. Let M be a maximum independent set in G and let x ¢ M. Then Mis a maximum independent set in G —x. Proof The graph G — x is the subgraph of G induced by V \ {x}. Let M be a maximum independent set in G and let x ¢ M. Then M is an independent set inG—x. Of course, any independent set in G — x is also an independent set in 6. ‘Thus G — x cannot have an independent set M' with [M'| > [M| since this contradicts the assumption that M is a maximum independent set in G. This proves the lemma. 0 Lemma 1.3. Let M be a maximum independent set in G and let x € M. Then M \ (x) is @ maximum independent set in G — Nix) Proof. The graph H = G ~ N{x] is the subgraph of G induced by V \ Nix]. Let M be a maximum independent set in G and assume that x € M. Notice that M \{x) is an independent set in G — Nix). Suppose that H has an independent set M’ which is larger than M \(xJ. Since Mis an independent set in G — Nix], M’ contains no neighbors of x. Thus M’U(9)is an independent set in G which is larger than M and this contradicts the assumption, This proves the lemma. o In other words, Lemmas 1.2 and 1.3 show that, for any vertex x, a maxi- mum independent set M can be derived from a maximimum independent set in G — x or from a maximum independent set in G — Nix]. ‘The algorithm builds a rooted binary tree T as follows. The root of T cor- responds with the graph G. If the graph has only one vertex, then T consists of the root only. Otherwise, choose a vertex x in G. The root has two children. 4 1 Exponential Algorithms ‘The left child is the root of a binary tree which corresponds with the graph G—x. The right child is the root of a binary tree which corresponds with the sraph G — Nix} Our algorithm computes a maximum independent set in G as follows. If G has only one vertex then a(G) = 1. Otherwise, the algorithm recursively computes the maximum independent set in the left subtree and in the right subtree. By the two lemmas above, (6) = max ( a(G —x), 1+ «(6 — Nil) } aay We need to make a remark here. If x is the only vertex in G then G —x is not a graph since, by definition, a graph has at least one vertex. (The ‘empty graph’ is the graph without any edge.) In Formula (1.1), if V = (x) then we define «(G — x) = 0. A similar situation occurs when x is adjacent to all other vertices, ie., when N[x] = V. In that case we define «(G — Nix]) = 0. For example, assume that the graph G is a clique. A clique is a subset C of vertices such that every pair of vertices in C is adjacent. In other words, a clique in the graph is an independent set in the complement G of the graph G and vice versa. Since G isa clique, any maximal independent set in G has only one vertex. ‘Thus G has exactly n maximal independent sets. In this case, every pair of vertices in G is adjacent, thus N[x] = V for any vertex x. Ifx is the only vertex in G then a(G —x) = 0 and otherwise a( — x) = 1. In order to obtain a good timebound we like to reduce the graph in at least one of the two branches as much as possible. One branch only removes the vertex x and this reduces the graph by one vertex. The other branch removes INbxl| vertices from the graph. To make this graph as small as possible we choose the vertex x such that it has the largest degree. Lemma 1.4. Let G be a graph and assume that every vertex of G has degree at ‘most 2. Then a maximum independent set in G can be computed in linear time. Proof. Since every vertex has degree at most 2, the graph is the union of a collection of paths and cycles. ‘To compute the maximum independent set of G we can compute the maxi- mum independent set in each of the (connected) components. of G and add them up. We leave it as an exercise to check the following claims, for example by using (1.2) ‘The length of a path or cycle is the number of edges in the path or the cycle. ‘An isolated vertex in G is a vertex without neighbors. 1.1 Independent set 5 (1) If Cis cycle of length 2k then «(C) (2) If Cis.a cycle of length 2k + 1 then a(C) = k. (3) If Pis a path of length 2t > 0 then a(P) = €+1. (4) If Pisa path of length 2¢ +1 > 0 then a(P) =¢+1. k ‘Thus, in order to compute «(G) it suffices to compute the lengths of the com- ponents of G, and this can be done in linear time. Oo ‘We now change the algorithm a litte bit, as follows. As long as there exists a vertex x in the graph with degree at least three, then the algorithm chooses such a vertex to build the tree T. When, at some point, a reduced graph H. has no more vertices of degree more than two then the algorithm uses the linear-time algorithm described in Lemma 1.4 to compute a(H). Let T(n) be the worst-case timebound that the algorithm needs to com- pute a(G) for a graph G with n vertices. Then, by the Formula (1.1) and by Lemma 1.4 we have the following recurrence relation for Tin). T(n) < Tin—1) + Tin 4) + O(n +m) a2) Perhaps you wonder why we write T(n — 4). If x is a vertex of degree i then the Formula (1.1) says T(n — i— 1) instead of T(n — 4). However, notice that T(n) is a non-decreasing function (see Exercise 1.3), and since the degree of xis at least three i23 > Tin yj1 Suppose that T(n — 1) > T(n) for some n > 1. We obtain a contradiction as follows. (@) Let G be a graph with n—1 vertices. Let G’ be the graph obtained from G by adding an isolated vertex to G. Prove that a(6') = a(G) +1. (b) Show that this proves that the maximum independent set problem for G can be determined in T(n) time. This contradicts the assumption that Tin=1) > Tin). 14. Find a linear-time algorithm which checks if a graph is bipartite. 15. Find an exact algorithm for 4-coloring, 1.6. Check Formula (1.4) on Page 9. 1.7. Check Formula (1.5) on Page 10. 1.8 Problems 17 1.8. Let G (V,E) be a graph. (a) A Hamiltonian cycle is a cycle in G which contains all vertices. Show that there is an O*(2") algorithm which solves the Hamiltonian cycle problem. Hint: Reduce the Hamiltonian cycle problem to the traveling salesman problem. For any two vertices i and j in G define ‘ 1 iff,i)e E and ati = 1.16) i { HIE ey (b) A Hamiltonian path is a path in G which contains all vertices. The differ- ence with the Hamiltonian cycle problem is that the two endpoints of the path are not necessarily adjacent. Design an O*(2") algorithm that solves the Hamiltonian path problem on graphs with n vertices. 1.9. Check the Formulas (1.10) and (1.11) and show that the sets f(X,), a8 defined by these formulas, can be computed in 0*(2™'}. 1.10. The subset sum problem described in Section 1.7 is NP-complete. The- orem 1.25 on Page 15 shows that it can be solved in O(K -) time. Does this prove that P= NP? viizessy Google 2 Graph Classes In this chapter we have a close look at a few important graph classes and we look at some [Link] problems that become polynomial when the graphs are restricted to these. A graph class, or a class of graphs, is simply a set of graphs. For example 9 =(G |G isa planar graph ) (ay is the class of all planar graphs. A class of graphs may be finite or infinite. The class above, of all planar graphs, is of course infinite (it contains an infinite number of elements) Obviously, many NP-complete problems can become polynomial when one restricts the graphs to some special graph class. For example, the four-coloring problem is NP-complete but it can be solved trivially when one restricts the staphs to the class of planar graphs. For algorithmic problems one considers usually only infinite classes of graphs. The reason is that for finite classes of graphs most problems can be solved in constant time by exhaustive search. Usually, one restricts the research on infinite classes of graphs to classes that are hereditary. A class § of graphs is hereditary if G € $implies that every induced subgraph of G is also in S. For example, the class of planar graphs is hereditary, since if G is planar then so is every induced subgraph of G. All the classes that we study in this chapter are hereditary. When one studies some graph class then the membership of graphs in Gis an important issue. One refers to this as the recognition problem for the class § Input: A graph 6. Question: Is G € $? 20 2 Graph Classes For example, the planar graphs are recognizable in linear time, but there are many classes of graphs for which the recognition problem is not clear. For example, consider the class ‘93 =( G | G is a planar graph and x(G) <3 }. ‘The recognition problem for 3 is NP-complete, since the 3-coloring problem is NP-complete for planar graphs. A lot of research is done on subclasses of perfect graphs. All classes that ‘we study in this chapter are perfect. We introduce the class of perfect graphs in the next section. 2.1 Perfect graphs Definition 2.1. A graph G is perfect if for every induced subgraph H of G xiH) = @(H), where x(H) is the chromatic number of H and w(H) is the clique number of H. fone wants to color a graph G such that adjacent vertices have different colors, then all vertices of a clique in G must receive different colors. Thus for all graphs we have x(G) > w(6). 22) For perfect graphs equality holds, not only for the graph itself but also for all induced subgraphs of it. Notice that the class of perfect graphs is hereditary, simply by definition. Perhaps we should emphasize this. Assume that for some graph G, x(G) > w(6). For example, if G is an odd cycle of length more than 3 then x(G)=3 and w(G) =2. It is easy to construct a graph G! such that x(G‘) = w(G') by adding a clique of size at least x(G) to G. The graph G! is of course not perfect, since G is an induced subgraph of G! and equality in (2.2) does not hold for G. Since the structure of G’ is not essentially different from the structure of G itcannot be expected that there are many problems that are easier to solve for 24 Perfect graphs 21 than for G. For example, a dominating set for G’ consists of a dominating set in G plus one vertex in the clique that is added to G. Thus the dominating set problem for G’ is just as hard as itis for G. ‘The complement of a graph G is the graph G with the same set of vertices as G, and with two vertices in G adjacent if and only if they are not adjacent in G. Concerning perfect graphs one of the first and most important theorems ‘was proved by Lové[Link] 1972.1 ‘Theorem 2.2 (The perfect graph theorem). The complement of a perfect graph is perfect. ‘Thus, if G is perfect then for every induced subgraph H of G we have that ‘@(H) = «(H), (23) ‘where x(H) = x(F1) is the smallest number of cliques that partition the set of, vertices and a(H) = w(H1) is the cardinality of a largest independent set in H. In Exercise 2.2 we ask you to prove that bipartite graphs are perfect. By ‘Theorem 2.2 also the complements of bipartite graphs are perfect. (Can you prove this without using Theorem 2.2?) Another important example of perfect graphs is the set of linegraphs of bipartite graphs. The linegraph L(G) of a graph G has as its vertices the edges of G and as its edges those pairs of edges in G that share an endpoint. ‘As an introductory example, let us prove that linegraphs of bipartite graphs are perfect. Lemma 2.3. Let G be bipartite. Then L(G) is perfect. Proof First of all, itis sufficient to prove Equation (2.3) for L(G), since re- moving an edge from a bipartite graph leaves it bipartite. (That is, the class of linegraphs of bipartite graphs is hereditary.) Notice that an independent set in L(G) is a set of edges in G of which no two share an endpoint, ie., a(L(G}} = 1G), where v(G) is the cardinality of a maximum matching in G. One of the earliest results in graph theory is the Theorem of Kénig-Egervéry:? TT. Lovase, Normal hypergraphs and the perfect graph conjecture, Discrete Mathe- ‘matics 2 (1972), pp. 253-267. *D. K6nig, Graphen und Matrizen, Math. Lapok 38 (1931), pp. 116-119, 22 2 Graph Classes If G is bipartite then v(G) = +(G), where 1(G) is the cardinality of a smallest vertex cover in G. A vertex cover is a set C of vertices such that every edge in G has at least one endpoint in C. Let C = {x1,...,%s) be a vertex cover of G. The set L; of edges that have the vertex x; in common forms a clique in L(G). Since C is a vertex cover, every edge in G is in some L;. Thus (Ly,...,L,) is a clique cover in L(G). Possibly some pairs Li and L, are not disjoint, but itis easy to change the clique cover into a partition of the vertices of L(G) into s cliques. ‘Thus, if C is a minimum vertex cover then a(L(G)) = v(6) = x(6) = |C|> x(L(G)) > a(L(G)), since, by (2.2), «(H) < «(H) for any graph H. Thus a{L(G}} = x(L(G)) and by Theorem 2.2 this proves the lemma, 0 Obviously, if a graph G is perfect then it cannot have an induced odd cycle of length at least five. By Theorem 2.2, when G is perfect it cannot have the complement of an induced cycle of length atleast five as an induced subgraph. Claude Berge conjectured in 1961 that this characterizes perfect graphs.’ The proof of the conjecture sent a shock wave through the graph theory community.* Definition 2.4. Let G be a graph. A hole in G is an induced cycle of length at least five. An antihole in G is an induced subgraph of G which is isomorphic to the complement of a cycle of length at least five. An odd hole in G is a hole of ‘odd length. An odd antihole is an antihole of odd cardinality. Theorem 2.5 (The strong perfect graph theorem). A graph is perfect ifand only if it has no odd hole and no odd antihole. ‘Theorem 2.5 was proved using a certain decomposition of the graph into four basic classes of perfect graphs, namely, (2) bipartite graphs, (2) complements of bipartite graphs, (3) linegraphs of bipartite graphs, and (4) complements of linegraphs of bipartite graphs, * C, Berge, Farbung von Graphen, deren simtliche baw. deren ungerade Kreise starr sind, Wiss, Zetschr: Martin-Luther Univ, Halle-Wittenberg 10 (1961), pp. 114-115. “M, Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfeet graph theorem, Annals of Mathematics 164 (2006), pp. 51-229. 2.2 Cographs 23 This decomposition theorem for perfect graphs also led to a polynomial algorithm for recognizing perfect graphs.° Theorem 2.6. There exists an O(n?) algorithm which tests if a graph with n vertices is perfect. One of the reasons for the popularity of perfect graphs is the following theorem.® ‘Theorem 2.7. There exist polynomial algorithms to compute w(G) and x(G) for graphs G that satisfy w(G) = x(G) ‘The Shannon capacity of the complement of a graph is a graph parameter which is sandwiched between the clique number and chromatic number. In tum, the Lovasz number is sandwiched between the Shannon capacity and the clique cover number. Thus, if we write @(G) for the Shannon capacity and 6(G) for the Lovasz number, then (6) = a(6) < @(G) < 8(6) < KG) = x(6). (24) ‘The theorem above was proved by showing that the Lovsz. number 8(6) of a graph G is computable in polynomial time.” 2.2. Cographs One of the most elegant classes of graphs is the class of cographs. Definition 2.8. A graph G is a cograph if it has no induced P4, which is a path with four vertices. Fig. 2.1. A Py isa path with four vertices. Notice that Py By definition, the class of cographs is hereditary, namely, if G has no in- duced P, then no induced subgraph of G has an induced Ps, * M, Ghudnovsky, G. Comnugjols, X. Liu, P. Seymour and K. Vu8kovié, Recognizing Berge graphs, Combinatorica 25 (2005), pp. 143-186. © M, Grotschel, L. Lovase and A. Schrijver, Polynomial algorithms for perfect graphs. In Berge, Chvatal eds.): Topics on perfect graphs, North-Holland Math. Stud. 88 (1984), pp. 325-356. 7 L, Lovise, On the Shannon capacity of a graph, IEEE Transactions on Information ‘Theory 25 (1979), pp. 1-7. 24 2 Graph Classes Lemma 2.9. If G is a cograph then G is perfect. Proof Let G be a cograph. We show that G nor G has a hole (an induced cycle of length at least 5). The graph G has no hole, otherwise it has an induced Py. Notice that Py is isomorphic to Ps. Thus if G is a cograph then G is also a cograph. Thus G has no antihole. Since G has no hole it has no odd hole and the same holds true for G. The claim now follows from Theorem 2.5. Oo ‘Theorem 2.10. A graph G = (V, E] isa cograph ifand only if for every induced subgraph H of G one ofthe following properties holds. (2) H has only one vertex, or (b) H is disconnected, or (© His disconnected. Proof. Notice that F, then G is a cograph, isomorphic to Py. This implies that if G is a cograph ‘A graph with less than four vertices is a cograph. Therefore, since the class of cographs is hereditary, itis sufficient to prove that G or G is disconnected when G is a cograph with atleast two vertices. Itis easy to check that the claim holds true when G has at most three vertices. ‘Assume that G has at least four vertices. Assume also that G is connected, Let x be a vertex of G. By induction G — x or the complement of G — x is, disconnected. ‘Assume that G — x is disconnected and let C1,...,Cy be the components of G — x. Assume that x has a neighbor and a nonneighbor in C1. Then there exist vertices a and b in C; such that [a,b,x] is an induced Ps in G. Since G is connected, x has a neighbor ¢ in C2. Now [a,b,x,c] is an induced Py which is a contradiction, Thus x is adjacent to all other vertices in G. Then G isconnected, since {x} is a component of G. Assume that the complement of G — x is disconnected. (We now ‘copy’ the argument above.) Let Ci,...,C’, be the components of the complement of G — x. Assume that x has a neighbor a’ and a nonneighbor b’ in Cj. Since GIC{] is connected and since there is no induced Ps, a’ and b’ are nonadjacent inG. If x is adjacent to all vertices in C, then G is disconnected with a component C4, Thus x has a nonneighbor cin C2. Now [x,a',c’,}/] is an induced Py, which is @ contradiction. ‘Thus we may assume that x is not adjacent to any other vertex in G, and so G is disconnected. ‘This proves the theorem. o 2.2 Cographs 25 2.2.1 Cotrees Let G be a cograph. By Theorem 2.10 we can build a decomposition tree for the graph G. ‘The decomposition tree is a pair (T,f) where T is a binary tree and f is a bijection from the leaves of T to the vertices of G. Each internal node, including the root, is labeled with a - or an ®-operator. Consider an internal vertex t. Let Vi and Ve be the two sets of vertices in G that are mapped to the leaves of the left - and right subtree. If tis labeled with © then every vertex of Vj is adjacent to every vertex of V2. If tis labeled by & then no vertex of Vi is adjacent to any vertex of Va. Let G be a cograph. We can build a decomposition tree as follows. If G has only one vertex, the tree consists of a single leaf, which is mapped by f to the vertex of G, Otherwise, by Theorem 2.10, either G or G is disconnected. Assume that G is disconnected and let C:,...,Ct be the components of G. Group the components into two nonempty sets, say A and B. Recursively, build decomposition trees (T;, f;) and (Ta, fz) for GIA] and G[B]. Create a new root, and make it adjacent to the root of T; and to the root of 1. Label the new root by &. _ Assume that G is disconnected. In that case, build a decomposition tree (7,4) for G as described above. Change all labels from & to © and vice versa. ‘A decomposition tree for cographs as described above is called a cotree. Notice that a graph G is a cograph if and only if it has a cotree (see Exer- cise 2.6). Corneil, Perl and Stewart proved the following theorem.* ‘Theorem 2.11. There exists a linear-time algorithm that recognizes cographs. When G is a cograph then this algorithm builds a cotree for G. 2.2.2. Finding cliques in cographs ‘To illustrate the usefulness of cotrees, we show how to use it for the compu- tation of the clique number. ‘Theorem 2.12. There exists a linear-time algorithm that computes the clique umber «(G) of a cograph G. *D. Corel, ¥. Perl and L. Scuwart, A linear recognition algorithm for cographs, SIAM Journal on Computing 14 (1985), pp. 926-934. 26 2 Graph Classes Proof let G = (V,E) be a cograph. First, the algorithm builds a cotree (T, f) for G. By Theorem 2.11 this step takes linear time. First assume that G has only one vertex. Then (6 Now assume that |V| > 2. For an internal node p of T let Vj and V2 be the two sets of vertices that are mapped to the leaves in the left - and right subtree, Let Gi = G[Vi] for i {1,2} and let Gy = GIMU Val. First assume that the label of p in T is @. Then Gp is the join of G1 and G2, that is, every vertex of Gy is adjacent to every vertex of Gz. Notice that (Gp) = (G1) + w(G2). (2s) Now assume that the label of p is ©. Then Gy is the union of G; and G2, that is, no vertex of G, is adjacent to any vertex of G2. Now (Gp) = max { (G1), (62) } (2.6) Assume that p is the root of T. The algorithm recursively computes w(G1) and (G2). Since p is the root, Gp = G and w(G) follows from Formulas (2.5) and (2.6), ‘The amount of work in each internal node takes O(1) time. So, in total the algorithm runs in time O(n), where n = |V\, since the depth of the cotree is at most n. In other words, when the cotree is a part of the input this algorithm runs in O(n) time. This proves the theorem. o 2.3 Distance-hereditary graphs Oo<, HH & Fig, 2.2. A graph is distance hereditary if it has no induced house, hole, domino or gem, Edward Howorka introduced distance-hereditary graphs.? ° E, Howorka, A characterization of distance hereditary graphs, The Quarterly Journal of Mathematics 28 (197), pp. 417-420, 2.3 Distance-hereditary graphs 27 Definition 2.13. A graph G is distance hereditary if for every pair of nonadja- cent vertices x and y and for every connected, induced subgraph H of G which contains x and y, the distance between x and y in H is the same as the distance between x and y in G. In other words, a graph G is distance hereditary if for every nonadjacent pair x and y of vertices, all chordless paths between x and y in G have the same length. (A path P is chordless if GIP] is a path; that is, P has no short- cuts.) Notice that, by definition the class of distance-hereditary graphs is hered- itary, ‘There are various characterizations of distance-hereditary graphs. One of them states that a graph is distance hereditary if and only if it has no induced house, hole, domino or gem. Distance-hereditary graphs are also characterized by the property that ev- ery induced subgraph has either an isolated vertex, or a pendant vertex, or a twin, An isolated vertex is a vertex with no neighbors. A pendant vertex is a vertex with exactly one neighbor. A twin is a pair of vertices x and y such that either N(x} =N(y) or Nix = Nil Let G be distance hereditary and let G’ be the graph obtained from G by adding an isolated vertex or a pendant vertex, or a twin x of some vertex y in G. In Exercise 2.10 we ask you to check that G is also distance hereditary. ‘Theorem 2.14. Distance-hereditary graphs are perfect. Proof Let G = (V, E) be distance hereditary. Then G has no hole. It remains to show that G has no odd antihole. Let x € V be a vertex which is either isolated, or a pendant adjacent to some vertex v, ot a twin of some vertex y. Consider G — x. By induction we may assume that G ~ x has no odd hole or odd antihole. Assume that G has an odd antihole H. Let V’ be the vertex set of H. Then x € V. Since H is connected, x is not isolated. Since H is biconnected, x is not a pendant vertex. Thus x is a twin of some vertex y. Notice that y ¢ V’ is, not a vertex of H, since H has no twins. Let V" = (V'\ (3) Uy). ‘Then V" induces an odd antihole in G — x whi This proves the theorem. o 28 2 Graph Classes 2.3.1 Decomposition trees for DH-graphs ‘A decomposition tree for a graph G = (V,E) is a pair (T,f) consisting of a rooted binary tree T and a bijection f from V to the leaves of T. When G is distance hereditary it has a decomposition tree (T,f) with the following three properties."° Consider an edge ¢ = {p,c} in T where p is the parent of c. Let We CV be the set of vertices of G that are mapped by f to the leaves in the subtree rooted at c. Let Qe C We be the set of vertices in We that have neighbors in G — We. The set Qe is called the twinset of e. The first property is that the subgraph of G induced by Qe is a cograph for every edge e in T. Consider an internal vertex p in T. Let ¢; and cz be the two children of p. Let e; = {p,c1) and let e2 = {p,ca}. Let Q and Q2 be the twinsets of e, and 2. The second property is that there is a join- or a union-operation between Qi and Qz. Thus either all vertices of Q: are adjacent to all vertices of Qa, or they are not adjacent to any vertex of Qa. As in cotrees, there is a label @ or @ at the vertex p in T that indicates which operation is performed on Qy and. Qa Remark 2.15. Notice the difference with the labels in cotrees. The &- or @- operator in the decomposition tree for distance-hereditary graphs works on the twinsets, and not, as in the cotrees, on all the vertices of We, and We, Let p be an internal vertex of T which is not the root. Let e be the line that connects p with its parent. Let Q. be the twinset of e. Let ¢, and cz be the two children of p in T. Let e: = {p,es} and let ex = {p,cz}- Let Qi be the twinset of e, for i € (1,2). The third, and final, property is that Qeae OF Qe=Qi OF W=W or Q= {WU ‘The vertex p in T has an extra label that indicates which of these four opera- tions that define Qe occur. Notice that the first property is a consequence of the other two. As an example, notice that cographs are distance hereditary. A cotree is a decompo- sition tree for a cograph with the three properties mentioned above. Lemma 2.16. Let G be distance hereditary. Then G has a decomposition tree as described above. © p, Hammer and F, Maffray, Completely separable graphs, Discrete Applied Mathe- ‘matics 27 (1990), pp. 85-99. 2.3 Distance-hereditary graphs 29 Proof Let G = (V,E) be distance hereditary. We use the property that G has an isolated vertex, a pendant vertex or a twin, Let x be an isolated vertex, a pendant vertex with neighbor y, or a twin of a vertex y, Let G’ = G — x. By induction G’ has a decomposition tree (7’,) as, described above. We now show how to construct a decomposition tree (T, ) for G. First assume that x is a twin of a vertex y. The vertex y is mapped by f’ to some leaf € of T’. Greate two leaves (, and ¢2 and let € be the parent of 1 and t in T. Let f map x to ¢ and y to G, and let f be the same as 1" for all other vertices z € V \ {x,y}. If x and y are adjacent, then the new intemal, node € receives an @-operator and otherwise it receives an &-operator. Finally, update the twinsets by adding x to all twinsets that contain y. The edges (t,:) and {€, 2} have twinsets (x) and (y). Assume that x is a pendant vertex with a neighbor y. The tree T and the map f are obtained in the same manner as described above. The internal node ¢ receives an @-operator since x and y are adjacent. Finally, x appears in only one twinset, namely in the twinset of the new edge {t,} in T. Assume that x is isolated in G. Choose an arbitrary vertex y in V \ (x). Create the tree T and the map f as above. In this case, the vertex x appears in no twinset. This proves the lemma. o When G is distance hereditary then a tree-decomposition for G with the three properties described above can be obtained in linear time, 2.3.2 Feedback vertex set in DH-graphs ‘To illustrate the usefulness of the decomposition tree for DH-graphs we show how it is used to solve the feedback vertex set problem. Definition 2.17. Let G = (V,E) be a graph. A set F.C Visa feedback verter set if G —F has no cycles, that is, G — Fis a forest. Let G be a graph. The feedback vertex set problem asks for a feedback vertex set in G of minimal cardinality. The feedback vertex set problem is NP-complete. A graph G is a join of two graphs Gy and Gz if G is obtained from the graphs G, and G, by making every vertex of G, adjacent to every vertex of Ga, A graph G is the union of two graphs G; and G2 if 30 2 Graph Classes 1. the vertex set of G is the union of the vertex sets of G, and G2, and 2. the edge set of G is the union of the edge sets of G, and Ga. Lemma 2.18. If G is the join of G1 and Gy and if Fis a feedback vertex set of G then IM-Fi<1 or (V2—F/<1 orboth. Proof Otherwise G — F contains a 4-cycle. o Lemma 2.19. Let G be a cograph which is the join of cographs G) and Go. Let F be a feedback vertex set of G. Assume that |v, —F| = 1. Then G2 — F is an independent set. Proof Otherwise G ~ F contains a triangle. 0 ‘Theorem 2.20. There exists a linear-time algorithm that solves the feedback vertex set problem on distance-hereditary graphs. Proof Let G = (V,E) be distance hereditary. First construct a decomposition tree (T,f) for G. This takes linear time. Extend the tree with a new root and make the parent of the old root r this. new root 1 Define the twinset of the edge (r, as . For ease of description, call this new decomposition tree again (T, f). Let p be an internal vertex of T which is not the root rand let c: and c2 be the two children of p. Let WY; and W; be the two sets of vertices that are mapped to the leaves in the subtrees at c; and c2 respectively and let W = Wi U Wa. Let Qi © Wy and Qz © Ws be the two twinsets of {p, 1} and {p, ca}. The © or @ label at p indicates whether there is a join or a union of the two twinsets, Quand Q:. Let e be the edge in T that connects p with its parent p’ (possibly p’ = 1’) and let e: = (p, ci} for é € (1,2). The twinset Qe is either one of Qi of Q2, or it is QU Qs, or itis the empty set. In our dynamic programming algorithm we mai for each edge e in T with twinset Q in the following four values (2) the minimal cardinality of a feedback vertex set of GIW1; (2) the minimal cardinality of a feedback vertex set F of GIW/ such that Q-F induces an independent set; 2.4 Chordal graphs 31 (3) the minimal cardinality of a feedback vertex set F of GIW| such that [Q-Fl=1 and (4) the minimal cardinality of a feedback vertex set F of G[W/ with Qcr It is easy to see that these four values for an edge ¢ = (p,p') in T can be obtained from the values at the edges (p, c1) and {p,¢a) (see Exercise 2.11). The minimal cardinality of a feedback vertex set for G can be read from the first value ie, Item (1) above, at the root-edge (r,r) of the binary tree- decomposition, The completes the proof. 0 2.4 Chordal graphs One of the oldest classes of graphs that have been studied in great detail is the class of chordal graphs. Definition 2.21. A graph is chordal if it has no induced cycle of length more than three. For example, the class of chordal graphs contains all trees. Notice that, by definition, the class of chordal graphs is hereditary. Let's first prove that chordal graphs are perfect. ‘Theorem 2.22. Chordal graphs are perfect. Proof Let G = (V,E) be chordal. Then, by definition, G has no holes. We show that G has no antiholes. Since Cs = Cs any antihole must have at least six vertices. Notice that any cycle of length at least six has an induced 2K2, which is the complement of a 4-cycle. Thus G has no antihole. 0 Our first characterization of chordal graphs is in terms of minimal separa- tors. Definition 2.23. Let G = (V,E} be a graph and let x and y be nonadjacent vertices. A set SEV\ (xu) is an x, y-separator if x and y are in different components of G 32 2 Graph Classes Definition 2.24. An x, y-separator $ is a minimal x, y-separator if no proper subset of S is an x, y-separator. Definition 2.25. A set $ is a minimal separator if there exist nonadjacent ver- tices x and y such that S is a minimal x, y-separator. Remark 2.26, Notice that one minimal separator may properly contain an- other minimal separator. For example, consider a 4-cycle (a,b,c, d). Add a pendant vertex e adjacent to c. Then {a,c} is a minimal b, ¢-separator and {c) isa minimal a, e-separator. Fig. 2.3. This graph has a minimal separator contained in another one. ‘Theorem 2.27. A graph is chordal if and only if every minimal separator is a clique. Proof Assume that G = (V, ) is chordal. Let S be a minimal x, y-separator for nonadjacent vertices x and y in G. Let Cx and Cy be the components of G—S that contain x and y. Notice that every vertex of $ has at least one neighbor in C and at least one neighbor in Cy. To see this, assume some z € $ has no neighbors in Cx. Then S$ \ {2} is also a minimal x, y-separator. This contradicts the minimality of S, Now assume that $ is not a clique. Then $ contains two vertices a and b that are not adjacent. Consider two chordless paths P, and Py from a to b. One with internal vertices in C, and the other with internal vertices in Cy, A chordless path is a path without a chord, that is, the path is induced. (in Exercise 2.13 we ask you to prove that P, and P, exist.) The two paths together form an induced cycle of length at least four. ‘This proves the theorem. o Our second characterization of chordal graph: vertices. in terms of simpli 24 Chordal graphs 33 Definition 2.28. Let G induces a clique in G. 'V, E) bea graph. A vertex x in G is simplicial if N(x) ‘Theorem 2.29. A graph is chordal if and only if every induced subgraph has a simplicial vertex. Proof Let G = (V,E) be a graph, First assume that every induced subgraph of G has a simplicial vertex. Let Q be a subset of vertices such that G[Q) is a cycle of length at least four. Then GIA] is an induced subgraph of G without simplicial vertex. This is a contradiction, Now assume that G is chordal. Let x be a vertex such that the largest compo- nent C of G —NIx] is as large as possible. Let $ C N(x) be the set of neighbors of x that have a neighbor in C. Then $ is a minimal x,y-separator for any ye C. Thus $is a clique. ‘We claim that every vertex of v\icus) is adjacent to all vertices in S. Clearly, x is adjacent to every vertex in $ since $ C N(x). Assume that there exists a vertex ZeEV\(SUCULx)) which is not adjacent to some vertex s € S. Then CU {s} is contained in a component of G — Nlz since G[C] is connected and s has a neighbor in C. Thus G — Niz] has a component which is larger than C. This contradicts the choice of x. Let G'=6-(suc) By induction we may assume that G’ has a simplicial vertex 2. Let N'(z) be the neighborhood of z in G’. Then N’(z) is a clique. Notice that Ni} =N'(z)US. Now N(z) is simplicial, since (® Sis actique, and Gi) N‘(z) isa clique, and (Git) every vertex of N’(z) is adjacent to every vertex of S. This proves that 2 is simplicial in 6. 0 34 2 Graph Classes Definition 2.30. Let G = (V, E) be a chordal graph. A perfect elimination or- dering for G is an ordering of the vertices BeiyeseaXnl such that for t= by (xian nthe vertex x; is simplicial in the subgraph of G induced ‘Theorem 2.31. A graph is chordal if and only if it has a perfect elimination ordering. Proof This is an immediate consequence of Theorem 2.29. 0 In Exercise 2.17 we ask you to prove that a perfect elimination ordering in a chordal graph can be obtained in linear time. One of the oldest and eas- iest algorithms to do this is an algorithm of Tarjan and Yannakakis."' Their algorithm computes an ordering [x1,..., tn] of the vertices in any graph. This ordering is a perfect elimination ordering if and only if the graph is chordal. ‘Their paper describes first a linear-time algorithm that computes an order- 1g and next it describes a linear-time test to see if the ordering is a perfect climination ordering. ‘Their algorithm computes an ordering as follows. It labels the vertices one by one. In each step, the unlabeled vertex that has the most labeled neighbors is labeled next. Ties are broken arbitrarily (so, the first vertex to get a label is arbitrary). This produces the perfect elimination ordering backwards, ie., the last vertex that gets a label is the first vertex in the perfect elimination ordering. Lemma 2.32. Every chordal graph has at most n maximal cliques, where n is the number of vertices in the graph. Proof. Let G = (V,E) be a chordal graph. Let x be a simplicial in G. The only maximal clique in G that contains x is N[x). Thus all other maximal cliques in G are maximal cliques in G — x. The claim follows by induction. o TTR. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyelic hypergraphs, SIAM Journal on Computing 13 (1984), pp. 566-579. 24 Chordal graphs 35 2.4.1 Clique trees Chordal graphs have a special decomposition tree, which is called a clique tree. These clique trees can be defined in two ways. We describe both. Definition 2.33. Let G = (VE) be a graph. Let (T,8) be a pair where T is a tree and 8 is a collection of subsets of V which are in 1-1 correspondence with the vertices of T. For a vertex ‘in T Let Sy € 8 be the subset that is asigned to the vertex i. The pair (T, 8) isa clique tree for G if the following conditions are true. (2) 8 is the set of maximal cliques in G, and (b) for every vertex x € V, if x is in two subsets S\ and S, then x is in every Se ‘for which lies on the path in T from ito j, In other words, a clique tree for G is a tree of which the vertices represent the maximal cliques in G such that, for every vertex x in G, the maximal iques that contain x form a subtree of T. ‘Theorem 2.34. A graph is chordal if and only ifit has a clique tree. Proof. First assume that the graph G = (V,E) has a clique tree (T, 8). Let be a leaf in T and let $; € § be the maximal clique in G which is assigned to ¢. ‘We claim that S¢ contains a vertex which is simplicial in G. Let p be the neighbor of ¢ in T. The cliques S; and Sp are maximal cliques in G, so there must be a vertex ZESe\ Sp. ‘The maximal cliques that contain z form a subtree of T, by definition of the clique tree, Since z ¢ Sp, the vertex z is contained only in one maximal clique Se in G. Thus z is simplicial. ‘Assume that G = (V,E) is a chordal graph. We may assume that G is not a clique, otherwise we ate done. Let S be a minimal separator in G such that S| is as small as possible. Let Ci,-..5Ce be the components of G ~ S. Since $ is a minimal separator, there are at least two components. We claim that every vertex in $ has a neighbor in each Ci. Assume that s € S has no neighbors in C;. Let S'=S\ {5}. ‘Thus $’ is an x, y-separator for a pair ‘Then C; is a component of G xeC, and yeUt cy, ‘This contradicts the choice of S. 36 2 Graph Classes Consider clique trees T; for the subgraphs Gi of G induced by CLUS forie{l,...,th Since $ is a clique, it is contained in a maximal clique Mi in Gy. We leave it as an exercise to check that Mi # 5, since G is chordal. Construct a clique tree T for G as follows. For i = 2,...,t make the vertex in T, that represents M; adjacent to the vertex in 7; that represents My. ‘We prove that this is a clique tree for G. Let x € Ci. The maximal cliques that contain x are all contained in G;. Thus these form a subtree of T. Now let x € S. The cliques in Gj that contain x form a subtree of T; and Mi is one of them, By the construction, all the maximal cliques in G that contain x form a subtree of the clique tree T for G. This proves the theorem. 0 ‘The other way to describe clique trees is as follows. ‘Theorem 2.35. A graph G = (V,E) is a chordal graph if and only if itis the intersection graph of acollection of subtrees of a tree. By that we mean that there exists a tree T and a collection of subtrees {k|xeV) such that two vertices x and y of G are adjacent if and only if T and Ty have at least one vertex of T in common. Proof First assume that G is chordal. Consider a clique tree (T,$) for G. Let x be a vertex of G. By definition of the clique tree, the maximal cliques in G that contain x form a subtree Ty of T. Assume that two vertices x and y are adjacent in G. The edge {x,y} is con- tained in some maximal clique in G. So TN Ty # 2. Assume that x and y are two vertices and assume that p € T, Ty. The maximal clique S» which is assigned to the vertex p in T contains x and y. ‘Thus x and y are adjacent. Now assume that G is the intersection graph of a collection of subtrees of a tree T. Consider a leaf ¢ of T. If €is not in any subtree Tx, then we may remove the leaf from T. If every subtree that contains ¢ contains also the neighbor of ¢ in T, then we may remove ¢ from T. Finally, assume that there is a tree T. which consists of the single vertex ¢. If y and 2 are two neighbors of x, then Ty and T, both contain ¢, and so y and zare adjacent. That means that x is a simplicial vertex. Now remove x from the graph and T, from the collection of subtrees. It follows by induction that G has a perfect elimination ordering. By Theorem 2.31, is chordal. This proves the theorem. o 2.4 Chordal graphs 37 2.4.2. Algorithms for independent set, clique and vertex coloring in chordal graphs ‘Theorem 2.36. There exists a linear-time algorithm to compute a maximum independent set in chordal graphs. Proof. Let G = (V,E) bea chordal graph. Let s be a simplicial vertex in G. ‘We first prove that there exists a maximum independent set I in G which contains s, To see this, let I be a maximum independent set and assume that s ¢ I. If Nis} then I {s) is also an independent set, which is a contradiction, Since s is a simplicial vertex in G, N(s) induces a clique in G. Thus IN(s) = 1. Let w € N(s} 1. Then consider V=(1\ wuts). ‘Then I' is also @ maximum independent set and s € I’. ‘The algorithm computes a maximum independent set in G as follows. Take any simplicial vertex s and start with I = (s}. Now let G! =G-Nisl ‘Then G’ is chordal, and by induction there exists a linear time algorithm that computes a(6"). Then (6) =1+4(6') ‘This proves the theorem. o ‘Theorem 2.37. There exists a linear-time algorithm that computes «(G) for chordal graphs G. Proof Let G = (V, E) be a chordal graph. Then, by Theorem 2.31 on Page 34, G has a perfect elimination ordering bray seal Let Ny = INbal 9 fxi,.-.5%nll ‘Then w(G) = max (Ny |i € {1,...,0)} This proves the theorem. ao 38 2 Graph Classes Let G = (V,E) be a chordal graph. Then G is perfect, and x(G) = w(G} By Theorem 2.37 there exists a linear-time algorithm that computes x(G). An actual coloring is also very easy to obtain, as we show next. ‘Theorem 2.38. There exists @ linear-time algorithm that computes a vertex col- ‘ring for G with x(G) colors for chordal graphs 6. Proof Let G = (V,E] be a chordal graph. Let [x1,..-,%n] be a perfect elim- ination ordering for G. We color the vertices of G greedily with w(G} colors from the color set O=(1,..., w(6)} as follows. For i = n down to 1, color the vertex x; with an arbitrary color from Q that is not used by vertices in NO) AE Risa one mb an To see that this is possible, notice that the set in Formula (2.7) contains at ‘most «(G) ~ 1 vertices. Thus there is a color in Q. available to color x. ‘The claim follows by induction. a 2.5 Interval graphs ‘As far as practical applications are concerned, the class of graphs that steals the show is the class of interval graphs. Indeed, practical applications range from archeology, sociology, scheduling classes at school, DNA-sequencing problems in biology, time-schedules for airliners, et cetera, etc, &te. In this section we have a short look at the definition and some of the most important properties of interval graphs. Definition 2.39. A graph G is an interval graph if itis the intersection graph of a collection of intervals on the real line. By that we mean that there is an interval Iy for every vertex x in G such that two vertices x and y are adjacent in G ifand only fle Vly #2. Remark 2.40. We only look at finite graphs. Then it is easy to see that we can have intervals such that no two endpoints coincide. Thus the question ‘whether the intervals are closed or open is not an issue, Also, we may assume that all intervals are finite 25 Interval graphs 39 ‘Theorem 2.41. Interval graphs are chordal. Proof. It is not difficult to see that one cannot construct any cycle of length more than three as the intersection graph of intervals. If one interval Iy is completely contained in some other interval ly then, for the corresponding vertices x and y in G we have Nix C Nil. Consider a cycle [x1,..., 4). Suppose it has an interval representation. By the previous observation we may assume that O k? Any algorithm, exponential or not, that solves this parameterized clique number problem, can be used to solve the clique number problem: Just check for k = 1,...,.m whether G has a clique of k vertices, and determine the largest k for which it has, Just coming up with some parameter like that doesn't help much, of course. Well, maybe it does, a litte bit. Suppose that w(G) is at most two. For example, any bipartite graph has clique number at most two, so there are lots of them. It is easy to check if w(G) > 3: just run the following algorithm. 1. If G is an independent set then w(G) = 1. OF course, it takes only linear time to check if G has an edge or not. 2. When G has at least one edge, then the next step is to check if G has a triangle (x, y, 2} Ifs0, then w(G) is at least three. Ifnot, then w(6) <3. ‘To check if G has a triangle, we can check for every three vertices x, y and if (x,u,z} isa triangle or not. There are O(n} triples to check. If we use the adjacency matrix to represent G we can check if a given triple (x, v,2}

You might also like