I want to use Vertex Cover as a known $NP$-complete Problem for the reduction. The claim is that if a have a vertex cover in graph $G$ with size $\le k$, I will have a clique cover in $G^\prime$ with total number of cliques $\le k$

I want to reduce vertex cover problem to clique cover problem in the following way:

enter image description here

  1. For each edge in $G$, I will create a corresponding vertex in $G^\prime$. In the picture, each e$_i$ in G corresponds to v$_i$ in $G^\prime$ for $1\le i\le5$

  2. Two vertices in $G^\prime$ will be connected by an edge if their corresponding two edges in G have one vertex in common. For example, there is an edge between v$_1$ to v$_2$ as their corresponding edges e$_1$ and e$_2$ have one vertex in common which is a.

  3. Each clique in $G^\prime$ corresponds to a vertex in G and that vertex belongs to the vertex cover. For example, for the graph in picture I have vertex cover {a,c}. With vertex a, I get a clique {v$_1$, v$_2$, v$_5$} and with vertex c, I get clique {v$_3$, v$_4$} in $G\prime$.

Now I don't know how to prove No instance in opposite direction: If $G^\prime$ doesn't have a clique cover with $\le k$ cliques (i.e it needs at least $k+1$ cliques), $G$ doesn't have a vertex cover size which is $\le k$.

Can anybody shed some light on this issue?

  • $\begingroup$ Keep trying. Also, try to refute your claim in parallel. $\endgroup$ Feb 24, 2017 at 3:17

1 Answer 1


Your reduction is incorrect.

The problem is with your claim "Each clique in $G'$ corresponds to a vertex in $G$". This is false, because there could be a clique associated to two different vertices.

For example, consider a 3-clique $G = (\{v_1, v_2, v_3\}, \{v_1v_2, v_2v_3, v_1v_3\})$. The corresponding graph $G'$ is also a 3-clique, but the 3 edges don't have a unique common vertex. In this case, $G'$ has a clique cover of size $1$, but $G$ doesn't.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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