0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Ahh great answer! Don't think I could have come up with it myself unfortunately. I also understood why my initial thought of reducing from 3-Color won't work. Do you have any tips for solving these types of problems? $\endgroup$ – user475680 Aug 5 '15 at 6:04
  • $\begingroup$ @user475680 I modified my post to include the "tips" $\endgroup$ – user137481 Aug 5 '15 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.