3
$\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?

Improve this question
$\endgroup$
5
  • $\begingroup$ See here, for example: www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK3/…. $\endgroup$
    – Yuval Filmus
    Commented Jan 23, 2015 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
    Commented Jan 23, 2015 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
    Commented Jan 23, 2015 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
    Commented Jan 23, 2015 at 19:03
  • 1
    $\begingroup$ A good first step is making sure you understand all the definitions involved. $\endgroup$
    – Yuval Filmus
    Commented Jan 23, 2015 at 19:24

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, I didn't understand Vertex Cover well. Thank you $\endgroup$
    – Yeynno
    Commented Jan 23, 2015 at 19:19

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.