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$ – Yuval Filmus Feb 24 '17 at 3:17

Your Answer

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

Browse other questions tagged or ask your own question.