COMP0017 Intractability of COL
Robin 16, 2019
An instance (G,n) of the decision problem COL is an undirected graph G = (V,E) where V is the set of vertices and E ⊆ V × V is the set of edges, together with a positive integer n. It is a yes-instance if there is a colouring function f : V → {0,1,…,n−1} (think of {0,1,…,n−1} as a set of n colours) such that if (v,w) ∈ E then f(v) ̸= f(w).
1. Which of the following graphs are yes-instances and which are no-instance of COL?
Copyright By PowCoder代写 加微信 powcoder
(b)=no, (c)=yes, (d)=no, (e)=no,
2. By writing down a suitable piece of pseudo-code or otherwise prove that COL ∈ NP. Answer: Foreachv∈V pickf(v)∈{0,1,…,n−1};%non-det. bit
result = true;
For each (v,w) ∈ E if f(v) = f(w) then result = false;
return(result);
Algorithm runs in linear time. If G has an n-colouring then there is some run of the algo- rithm that returns true so (G,n) is accepted. If G has no n-colouring then all runs of the algorithm return false so (G, n) is rejected. Hence the algorithm runs in p-time and solves COL.
3. Define CNF-SAT.
Answer: An instance is a propositional formula consisting of a conjunction of clauses each
Answer: (a)=no,
of which is a conjunction of literals. Such an instance is a yes-instance if there is some valuation making the formula true and it is a no-instance otherwise.
4. ProvethatCOL≤p CNF−SAT.
Answer: Let (G, n) be any instance of COL, where G = (V, E). We define a CNF formula φ(G, n) as follows. We use propositions pi,v for each i < n and each v ∈ V , so the number ofpropositionsis|V|×n. Foreachv∈V makeaclauseCv =i