2
$\begingroup$

I read on the internet that it's possible to reduce clique to vertex cover. Almost everyone use this theorem:

if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of size $n-k$, where $n$ is the number of vertices.

Consider the graph on five vertices and the following edges: a clique on $\{1,2,3,4\}$ and $(1,5),(2,5),(3,5)$. The complement of this graph has only one edge, and it does not cover the set of vertices.

Is the statement I quoted correct?

$\endgroup$
  • $\begingroup$ See here, for example: www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK3/…. $\endgroup$ – Yuval Filmus Jan 23 '15 at 18:43
  • $\begingroup$ So, I can reduce Clique to Indepdent Set and then to Cover Set Problem. Unfortunately, I don't see what is wrong with my above explanation $\endgroup$ – Yeynno Jan 23 '15 at 18:58
  • 1
    $\begingroup$ Work through the reduction and you'll what, if anything, goes wrong. It's best if you did it on your own. $\endgroup$ – Yuval Filmus Jan 23 '15 at 19:00
  • $\begingroup$ I tried to do this on my own and I failed, because I found counter-example that it doesn't work $\endgroup$ – Yeynno Jan 23 '15 at 19:03
  • 1
    $\begingroup$ A good first step is making sure you understand all the definitions involved. $\endgroup$ – Yuval Filmus Jan 23 '15 at 19:24
1
$\begingroup$

You're misunderstanding what Vertex Cover is: the task is to find a set of vertices which "cover" or "touch" all edges. Each of the vertices $4,5$ covers the unique edge $(4,5)$ in the complement of your graph.

The theorem states that the size of the maximum clique in a graph equals the size of a minimum vertex cover in its complement. This is because a set $A$ of vertices is a clique in a graph $G$ if and only if its complement $\overline{A}$ is a vertex cover in the complement graph $\overline{G}$.

Indeed, $A$ is a clique in $G$ if any two $x,y \in A$ are connected in $G$; $\overline{A}$ is a vertex cover in $\overline{G}$ if for every edge $(x,y) \in \overline{G}$, one of $x,y$ is in $\overline{A}$. So $\overline{A}$ is not a vertex cover in $\overline{G}$ if there exists an edge $(x,y) \in \overline{G}$ such that $x,y \notin \overline{A}$, i.e. if for some $x,y \in A$, $(x,y) \notin G$; this is exactly the condition that $A$ is not a clique in $G$.

$\endgroup$
  • $\begingroup$ Yes, I didn't understand Vertex Cover well. Thank you $\endgroup$ – Yeynno Jan 23 '15 at 19:19

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.