34-3 Graph coloring

Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph \(G = (V, E)\) in which each vertex represents a country and vertices whose respective countries share a border are adjacent. Then, a \(k\)-coloring is a function \(c: V \to \\{1, 2, \dots, k \\}\) such that \(c(u) \ne c(v)\) for every edge \((u, v) \in E\). In other words, the numbers \(1, 2, \dots, k\) represent the \(k\) colors, and adjacent vertices must have different colors. The graph-coloring problem is to determine the minimum number of colors needed to color a given graph.

a. Give an efficient algorithm to determine a \(2\)-coloring of a graph, if one exists.

b. Cast the graph-coloring problem as a decision problem. Show that your decision problem is solvable in polynomial time if and only if the graph-coloring problem is solvable in polynomial time.

c. Let the language \(\text{3-COLOR}\) be the set of graphs that can be \(3\)-colored. Show that if \(\text{3-COLOR}\) is \(\text{NP-complete}\), then your decision problem from part (b) is \(\text{NP-complete}\).

To prove that \(\text{3-COLOR}\) is \(\text{NP-complete}\), we use a reduction from \(\text{3-CNF-SAT}\). Given a formula \(\phi\) of \(m\) clauses on \(n\) variables \(x_1, x_2, \dots, x_n\), we construct a graph \(G = (V, E)\) as follows. The set \(V\) consists of a vertex for each variable, a vertex for the negation of each variable, \(5\) vertices for each clause, and \(3\) special vertices: \(\text{TRUE}\), \(\text{FALSE}\), and \(\text{RED}\). The edges of the graph are of two types: "literal" edges that are independent of the clauses and "clause" edges that depend on the clauses. The literal edges form a triangle on the special vertices and also form a triangle on \(x_i, \neg x_i\), and \(\text{RED}\) for \(i = 1, 2, \dots, n\).

d. Argue that in any \(3\)-coloring \(c\) of a graph containing the literal edges, exactly one of a variable and its negation is colored \(c(\text{TRUE})\) and the other is colored \(c(\text{FALSE})\). Argue that for any truth assignment for \(\phi\), there exists a \(3\)-coloring of the graph containing just the literal edges.

The widget shown in Figure 34.20 helps to enforce the condition corresponding to a clause \((x \vee y \vee z)\). Each clause requires a unique copy of the \(5\) vertices that are heavily shaded in the figure; they connect as shown to the literals of the clause and the special vertex \(\text{TRUE}\).

e. Argue that if each of \(x\), \(y\), and \(z\) is colored \(c(\text{TRUE})\) or \(c(\text{FALSE})\), then the widget is \(3\)-colorable if and only if at least one of \(x\), \(y\), or \(z\) is colored \(c(\text{TRUE})\).

f. Complete the proof that \(\text{3-COLOR}\) is \(\text{NP-complete}\).

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用