advertisement

Coloring Algorithms and Networks Graph coloring • Vertex coloring: – Function f: V C, such that for all {v,w} E: • f(v) f(w) • Chromatic number of G: c(G): minimum size of C such that there is a vertex coloring to C. • Vertex coloring problem: – Given: graph G, integer k – Question: Is there a vertex coloring of G with k colors? 2 Coloring Set coloring • Given: graph G=(V,E), set of colors C(v) C for all v V. • Question: is there a vertex coloring f of G with also for all v V: f(v) C(v)? 3 Coloring Set coloring is NP-complete • In NP: trivial. • Transform from 3-sat. Take a vertex for each variable, and a vertex for each clause. • C(xi) = {xi, not xi} • C(clause) = variables in clause • Coloring a vertex xi means setting that variable to the value not the color – E.g.: setting xi to true means coloring xi with (not xi) 4 Coloring Coloring is NP-complete • Transform from set coloring • Take instance of set coloring. Let C be set of all colors. • Add a clique with one vertex per color in C. • Add an edge between vertex v in original graph and color vertex c if c C(v) 5 Coloring Famous bounds • Four color theorem: – The chromatic number of a planar graph is at most four. • A graph is bipartite, if and only if it has chromatic number 2. • The chromatic number of a graph is at most the maximum degree of a vertex plus 1. – Improvement: Brooks’ theorem 6 Coloring Heuristics Greedy coloring • Take some permutation of the vertices. • for i = 1 to n do – Color the ith vertex with a color different from its colored neighbors. 7 Independent sets • k=1 • repeat until all vertices are colored – Find a (maximal) independent set of uncolored vertices – Color these with k – k++ Coloring Simple lemma • The chromatic number of a graph is the maximum of the chromatic number of its biconnected components. 8 Coloring Brooks’ theorem • Suppose G is a connected graph, with the maximum vertex degree D(G). Suppose G is not a complete graph or a cycle of odd length. Then c(GD(G). • Proof: – Suppose G is biconnected. (If not, see previous lemma; …) – Two cases. 9 Coloring Case 1: There are nonadjacent u and v with G – u – v disconnected Write k = D(G). Assume D(G) > 2. D(G1) k D(G2) k Induction: c(G1) k; c(G2) k. • Again two cases: • • • G1 u v G2 –… 10 Coloring Two cases Case 1a. In G1 and in G2, we have a k-coloring with u and w different colors. – Permute the colors in G2 and form a coloring of G by taking `union’ of colorings. 11 Case 1b. In G1 every k-coloring has the same color for u and for w. – u and w must have degree k-1 in G1. – u and w have degree 1 in G2. – There is a k-coloring of G2 with u and w the same color. – Permute the colors in G2 and form coloring of G. • Case 1c. In G2 every kcoloring has the same color for u and for w. Similar. Coloring Case 2: For all non-adjacent u, v, G – u – v is connected • Let v be vertex of maximum degree. • v must have non-adjacent neighbors u, w. (Why?) • G – u – w is connected. Choose spanning tree T of G – u – w. • Choose v as root of T. • Color u and w by 1, and then color the vertices in T in postorder, greedily. – k colors are sufficient: vertices except v have an uncolored neighbor; v has two neighbors with same color. QED 12 Coloring Coloring interval graphs • Sort vertices with respect to non-decreasing right endpoints • Greedy coloring with this ordering gives optimal coloring! – Number of colors equals maximum clique size 13 Coloring Non-approximability • Lund, Yannakakis, 1994 • There is an e>0: Unless P=NP, then no polynomial time algorithm with ratio ne 14 Coloring Chromatic index • Edge coloring – Problem statement – Vizings theorem: G is edge-colorable with D(G) or D(G)+1 colors – NP-complete to decide which holds of these two options. – Edge coloring equals vertex coloring of edge graph 15 Coloring Coloring and Sodoku • Solving a soduku – Model as precoloring extension problem – Translate to set coloring, or coloring 16 Coloring Networks and graphs are everywhere • If you are a carpenter, everything looks like a hammer 17 Coloring