Graph colouring, and other hard problems We motivate this lecture with a historical excursion: Besides the "7 bridges of Königsberg" problem, another milestone in the early development of graph theory is the "4 colour problem" which originated in the middle of 19th century, and remained unsolved for more than 100 years! Briefly, the task is to show that any political map can be coloured with just 4 colours. . . Easy? Not, and (unsuccessful, though) attempts to solve this simple looking question stimulated the development of most of the areas of contemporary graph theory. BTW, yet another historical excursion discovers the "chess knight" problem, much older than the two previous. Can you traverse the complete chessboard with a knight? And how does this very old question relates to modern graph theory? Brief outline of this lecture • Definition of a colouring of a graph. Basic properties. • Some variants of the colouring problems. • Hamiltonian cycle, and some other "difficult" problems. • Algorithmic complexity (and NP-compl.) of basic graph problems. _________x Hliněný, Fl MU Brr I: MA010: Barevnost a další ^ 7.1 Proper colourings and the chromatic number Imagine that a given graph models relations between objects, the neighbouring pairs being somehow similar, and in need of a distinguishing "colouring" which makes all adjacent pairs of different colours. How can this be formulated mathematically? c Definition: A (proper) colouring of a graph G with k colours is any assignment c:V{G)^{l,2,...,k}, such that every pair of adjacent vertices gets distinct colours, i.e. c(u) ^ c(v) for all {u,v}gE(G). Definition 7.1. The chromatic number of a graph G is the least integer x(G) sucn tnat C can be properly coloured with x(G) colours. The numbers 1,2,... ,k used to colour the vertices of a graph G are naturally called the (vertex) colours (it is easier than to say white, red, blue, black, etc). Notice that the chromatic number and colourings make sense only for loopless graphs! Parallel edges, on the other hand, do not matter at all. Lemma 7.3. Let G be a simple n-vertex graph. Then x(G) < n- ar,d sn equality holds if and only if G c; Kn is complete. s_ Petr Hliněný, Fl MU Brn Fl: MAOIO: Barevnost a další Example 7.4. What is the relation of the above graph colouring with "map colourings"? The map regions (assumed connected in the picture) are represened by the vertices of a graph, and neighbouring pairs of regions (sharing a section of a boundary) define the edges of this graph, as in the picture. The meaning of a proper colouring is now clear. We can, however, find a better colouring of our map, just looking at the derived graph as follows. 2 3 1 etr Hlinený, Fl MU Br -I: MAOIO: Barevnost a další Theorem 7.5. A nonempty gr. G has chromatic number 1 if and only if G is edge-less. G has chromatic number at most 2 if and only if G contains no odd cycles, c Proof: The first claim is trivial. : Considering the second one, we easily see that an odd cycle needs 3 colours. Conversely we may run a breadth-first search (BFS) through G from any v, and colour the vertices by their distance from v — alternatively giving colours 1, 2,1, 2,... Why this simple colouring works (is proper)? Notice that any failure (i.e. an edge of G between two vertices that got the same colour) would imply an existence of an odd-length closed walk in G, and that in turn forces an existence of an odd cycle, a contradiction. D etr Hliněný, Fl MU Br -I: MAOIO: Barevnost a další Greedy approach to graph colouring Definition: A graph G is k-degenerated if every subgraph of G contains a vertex of degree at most k. An example of a fc-degenerated graph is that of maximum degree fc, but there exist more fc-degenerated examples with much higher maximum degree. On the other hand, it is not enough for G just to have some vertex of small degree, c Theorem 7.6. Every k-degenerated graph can be greedily (and properly) coloured by k + 1 colours, c Proof: We pick any vertex v\ of degree < k, and we recursively colour the subgraph G — vi with k + 1 colours. Then we notice that the neighbours of v\ carry at most k distinct colours, and so we can properly colour also v\ with the remaining colour. D Very easy and nice, right? But the general situation with colouring algorithms will be much more difficult. Still, one slight strengthening is possible. >etr Hliněný, Fl MU Br Fl: MAOIO: Barevnost a další Theorem 7.7. Let G be a connected simple graph of maximum degree k > 2. Then x(G) < k with the only exceptions when G is an odd cycle or a complete graph. Proof (a sketch): For k = 2 this follows from Theorem 7.5. Let now k > 3. In one direction, x(Kk+i) = k+l. So assume that G is not complete, and that all degrees in G are equal k (since the greedy approach of Theorem 7.6 could be applied otherwise).d • In the first step, we find two non-adjacent vertices u,v with a common neighbour«;. \fG—{u, v} is not connected, we colour it parts separately by induction. • So G — {u, v} is connected. The second step argues that the graph H resulting from G — w by identifying u with v into one vertex is (k — l)-degenerated. c • Hence H can be greedily fc-coloured using Theorem 7.6. After we "split" into original u and v, we get a colouring of G — w having u,v of the same colour. Then w "sees" at most k—\ distinct colours in its neighbourhood of size k, and a proper colour can be chosen for w. D >etr Hlinený, Fl MU Br Fl: MAOIO: Barevnost a další Graphs of high chromatic number Thinking about graphs which cannot be coloured with few colours, the first ones coming to mind are the cliques. But what else, are these the only structures forcing high chromatic number? c No, we can even show that there exist triangle-free graphs of arbitrarily high chromatic number! Proposition 7.8. (Mycielski) The graph H obtained from any graph G by the following sketched construction has the chromatic number \(G) + 1, and H is triangle-free if G was. Even more, one can prove the following surprising result: Theorem 7.9. (Erdös) For any c, r > 0 there exists a graph of chromatic number at least c and not containing a cycle of length less than r. 7.2 Variants of colouring problems, and Hamiltonicity Definition 7.10. The edge chromatic number of a graph G. We are looking for an edge colouring ce(E(G)) —> {1, 2,..., k} such that no two edges sharing a vertex have the same colour. The least number k for which an edge colouring of G exists is called the edge chromatic number Xe(G). c Theorem 7.11. (Vizing) If G is a simple graph, then A(G) < Xe{G) < A(G) + 1. c For most of graphs, it actually holds A(G) = Xe(G). Can you easily come with graphs of the other kind? Still, the edge colourability problem remains very hard, and it is also related to the 4 colour problem. etr Hliněný, Fl MU Brno 8 Fl: MA010: Barevnost a další Definition 7.12. Choosability (the list chromatic number) of a graph G. Given is a graph G with an assignment of "colour lists" L : V(G) —> (fc) (fc-element subsets of colours). The task is to find a list colouring cch(V(G)) —> N such no two adjacent vertices receive the same colour, and moreover, cch(v) G L (v) for every vertex v. The least size k of the colour lists which guarantees an existence of a list colouring of G (against all choices of L) is called the choosability (list chromatic number) ch(G) of the graph G. c Proposition 7.13. For every integer k there exists a bipartite (chromatic number 2) graph of choosability greater than k. etr Hliněný, Fl MU Brno 9 Fl: MA010: Barevnost a další Hamiltonian graphs Definition: A cycle C in a graph G is called Hamiltonian if C spans all vertices of G. A Hamiltonian path P in G is defined analogously. A graph G is Hamiltonian if G contains a Hamiltonian cycle, c Though it may sound strange, the Hamiltonian cycle problem is also related to some attempts to solve the 4 colour problem. Theorem 7.14. (Dirac) Every graph on n > 3 vertices and with minimum degree > n/2 is Hamiltonian. etr Hliněný, Fl MU Brno 10 Fl: MAOIO: Barevnost a další AfP-completeness of many graph problems Recall the definition of the class MV - those decision problems for which there exists a polynomial certificate. The MV'-complete problems are those having the highest difficulty within the class MV, i.e. those to which every member of MV can be reduced. As we shall see, most of natural graph problems are MV-complete. We start the excursion from the following classical "master" problem: Problem 7.15. 3-SAT (a spec, version of satisfiability) The following problem is MV -complete: Input: Logic formula $ in a conjunctive normal form, such that every clause of $ contains < 3 literals. Output: Is there a valuation of the ^-variables that makes $ true? etr Hliněný, Fl MU Brno 11 Fl: MAOIO: Barevnost a další Problem 7.16. 3-COL (3-Colouring of graphs) The following problem is ATV-complete: Input: Graph G. Output: Can the vertices of G be properly coloured using three colours? Proof (a sketch): We show a polynomial reduction from 3-SAT. For a given G we construct a formula $: The basis of the graph is a triangle with vertices denoted by X,T,F. Each variable Xj in $ is assigned a vertex pair adjacent to X. Each clause of $ is assigned a subgraph on 6 vertices (three of them adjacent to T), as in the picture. Then the remaining free "halfedges" are joined together in the way corresponding to the literals in the clauses. (xi V -iXj V . ..) Then one may easily check that G has a 3-colouring iff $ is satisfiable. D 'Hliněný. Fl Ml : MAOIO: Barevnost a další Problem 7.17. IS (Independent Set) The following problem is MT'-complete: Input: Graph G, and an integer k. Output: Is there an independent subset of size (at least) k in Gl c Proof: We show a polynomial reduction from 3-COL. Let H be a graph on n vertices which should be 3-coloured. We set k = n, and construct a graph G made of three disjoint copies of H as shown : H Assume c : V(H) —> {1,2,3} is a 3-colouring of H. Then one can choose k = n independent vertices in G - for each v G V (H) choosing the c(v)-th copy of v in the graph G. Conversely, if I is an independent subset in G of size k = n, then every triangle Tv, v G V (H) intersects I just in one vertex. That determines the colour for v in H. ü _____________něny, Fl MU____________________________________________________I: MAOIO: Barevnost a další ^ Problem 7.18. VC (Vertex Cover) The following problem is MV'-complete: Input: Graph G, and an integer k. Output: Is there a vertex cover of size at most k in Gl c Proof: We show a polynomial reduction from IS. Notice that the complement C = V(G) \ I of an independent set I is actually a vertex cover. So the reduction works with the same graph G and with k = n — í. ü independent set vertex cover etr Hliněný, Fl MU Bri Fl: MAOIO: Barevnost a další Problem 7.19. DOM (Dominating set) The following problem is ATV-complete: Input: Graph G, and an integer k. Output: Is there a dominating set of size at most k in Gin Proof (a sketch): Given any graph H, we construct an input graph G for DOM as follows: For every edge e G E (H), a new vertex ve is added, forming a triangle with e. vertex cover dominating set Now a vertex cover (cf. Problem 7.18) of the former graph is the same as a dominating set in the latter graph. D etr Hliněný, Fl MU Bri Fl: MAOIO: Barevnost a další Problem 7.20. HC (Hamiltonian cycle, directed) The following problem is ATP-complete: Input: Directed graph G. Output: Can we find a directed cycle in G passing through all vertices?a Problem 7.21. HAM (Hamiltonian cycle) The following problem is MP -complete: Input: Graph G. Output: Can we find a (undirected) circuit in G passing through all vertices? Proof: It is an easy reduction from the previous problem HC. Each vertex v of a directed graph H is replaced with three vertices forming a path Pv in the graph G. then the directed edges coming into v are joined to the first vertex of Pv, and the edges leaving from v are joined to the last vertex of Pv. D etr Hlinený, hl MU Brn< Fl: MAOIO: Barevnost a další 7.4 The interesting story of Vertex Cover Consider the (at first glance) very similar problems of a vertex cover and of a dominating set in a graph, both among the classical 7VP-complete problems. Yet, we discover a huge difference between them, briefly outlined as follows, c • If, in the computational complexity analysis, we focus on the value of the input parameter k, then we still cannot solve Dominating Set in a better way than exhaustively checking (almost) all fc-tuples of vertices. Even when k is fixed small, say k = 10, 20, this an intractable problem, c • On the other hand, a Vertex Cover of size k can be decided by a very simple algorithm running in time 0(2k ■ n), which is quite usable for small fixed values of k, giving actually a linear time algorithm! etr Hliněný, Fl MU Brno 17 Fl: MAOIO: Barevnost a další Algorithm 7.23. fc-VC (Vertex Cover) For any fixed k we are solving the following problem. Input: Graph G. Output: Is there a vertex cover of size at most k in Gl c We initialize C = 0 and F = E (G). • If F = 0, then C is returned as a vertex cover. If, otherwise, \C\ > k, then the return value is "NO". • We pick an arbitrary edge f = uv G F, and for each of its ends x = u, v we do: - C' = C U {x}, and F' results from F by removing all edges incident with x in G. - This algorithm is called recursively for G, C and F'. c Finally, how many (self-)recursive calls occurs in Algorithm 7.23 altogether? Every call generates two further recursive calls, but only up to a fixed depth k. hence the total computing time is asymptotically only 0(2k ■ n), c Remark: The factor 2k can be improved by more careful choice of branching. (2006: 1.2738fc) str Hliněný, Fl MU Brno 18 Fl: MAOIO: Barevnost a další