I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams.
I have come across this problem and I'm having some difficulty with it:
Let $ G = (V,E) $ be an undirected graph. We say that a group $S\subseteq V\ $ is a $K_4-Cover\ $ if for every sub-graph of $G$ which is a $4-CLIQUE\ $ there is a vertex in $S$.
Let us look at the following language:
$K_4-COVER=\{\left\langle G,k \right\rangle : G\ has\ a\ K_4-Cover\ of\ size\ k \}$
Prove that the above language is NP-Complete
OK so we learned in the course to prove that languages are NP complete by showing 2 things: A polynomial validator (not sure if this is the correct term, but that's what we call it in the language I'm learning it in) and by reducing NP-Complete language to it.
I've been trying to find a reduction that works but I'm having some trouble. So far I've tried reducing from Vertex-Cover, Independent-Set, K-Clique, but to no meaningful solution.
I have an Idea using 3-Color and was hoping for some feedback:
Basically I want the reduction to take a 3-Colorable graph, take a copy of it - G', create a 4-clique and connect it to one of the vertexes, then it outputs $\left\langle G',1 \right\rangle$
The reasoning behind this is that in a 3-colorable graph there can't be a 4-clique, so I would have to add one. Connecting it to one of the vertexes of the original graph means that all the 4-cliques (there is only one of them) has a node in the group of size 1.
I feel that the idea that I have is kind of dodgy and missing something (maybe the reasoning is completely wrong), so I'm looking for some feedback and also any help if I'm wrong.
Any help is appreciated (clues are welcome!)
Thank you!
Let Vertex-Cover = $\{ <G, k> : G$ has a vertex cover of size k$\}$
Given an instance $<G(V, E), k>$ of Vertex-Cover construct an instance $<G'(V', E'), k+2>$ of $K_4$-Cover:
1) Set $V' = V \cup \{x, y\}$.
2) Set $E' = E$
3) Add the edge (x, y) to E'
4) For each edge $(u, v)$ in E', add the edges $(x, u), (x, v), (y, u), (y, v)$
What we have done is make every edge (u, v) in G part of a 4 clique in G' consisting of the vertices x, y, u and v.
Now, if G' has a vertex-cover of size k+2:
G must have a vertex cover of size k which covers all edges (u, v) in G.
So, either u or v or both must be in the vertex cover.
So, G has a $K_4$-Cover of size k.
Now, if G has a $K_4$-Cover S of size k:
$S \cup \{x, y\}$ would be a vertex cover of size k+2 for G'.
I'll leave the proof that the reduction can be done in polynomial time to you.
This is how I approached the problem:
1) Recognize that this is a "cover" problem.
2) What do you know about "cover" problems?
$\;\;\;\;$ Set Cover
$\;\;\;\;\;\;$ U is a set of elements $\{e_1, e_2,..., e_m \}$
$\;\;\;\;\;\;$ $S = \{s_1, s_2,..., s_n \}$ where each $s_i$ is a subset of U such that the union of the $s_i$ = U
$\;\;\;\;\;\;$ A Set Cover for U is a subset of S where the union of the elements = U
$\;\;\;\;\;\;$ That is, it is a subset of S whose elements cover U.
$\;\;\;\;$ Vertex Cover
$\;\;\;\;\;\;$ U is a set of edges $\{e_1, e_2,..., e_m \}$
$\;\;\;\;\;\;$ $S = \{v_1, v_2,..., v_n \}$ is a set of vertices
$\;\;\;\;\;\;$ A Vertex Cover for U is a subset of S that covers U
$\;\;\;\;$ K-Cover
$\;\;\;\;\;\;$ U is a set of 4-cliques $\{c_1, c_2,..., c_m \}$
$\;\;\;\;\;\;$ $S = \{v_1, v_2,..., v_n \}$ is a set of vertices
$\;\;\;\;\;\;$ A K-Cover for U is a subset of S that covers U
Now, you notice that the difference between Vertex-Cover and K-Cover is that U is a set of edges in one and a set of 4-cliques in the other.
So, you start thinking about how to "reduce" edges to 4-cliques...
You should also read about how to reduce Vertex-Cover to Set-Cover.
Hope it helps...