2
$\begingroup$

What is the relationship between the sizes of minimum sized vertex covers and complete graphs?

$\endgroup$
  • 2
    $\begingroup$ Can you edit your question to include the question in the body of the post? Also, I suggest you edit to clarify what you are asking. What kind of relationship are you thinking of? I'm not quite sure what you are asking. What are your thoughts? Have you worked through some examples to see what relationships you can find? Can you show us what you've found so far? That might help us understand what you're looking for and give you better answers. $\endgroup$ – D.W. Oct 27 '17 at 4:08
  • $\begingroup$ Finally, please ask only one question per post (so I suggest you remove the "Also" and post that as a separate question using the 'Ask Question' button). $\endgroup$ – D.W. Oct 27 '17 at 4:08
  • $\begingroup$ Alright I edited it. $\endgroup$ – dirtysocks45 Oct 27 '17 at 8:32
2
$\begingroup$

A set of vertices is a vertex cover iff its complement is an independent set.

Indeed, a set $S$ is a vertex cover if for all edges $(x,y)$, either $x \in S$ or $y \in S$.

Conversely, a set $S$ is an independent set if for all edges $(x,y)$, either $x \notin S$ or $y \notin S$.

Despite this strong relation between minimum vertex cover and maximum independent set, in some sense maximum independent set is much harder: while minimum vertex cover has several 2-approximation algorithms, it is NP-hard to approximate maximum independent set to within $n^{1-\epsilon}$.

Finally, let me mention that a set of vertices is an independent set in a graph iff it is a clique in the complement graph (formed by replacing edges by non-edges and vice versa). This gives a relation between minimum vertex cover and maximum clique on the complement graph.

$\endgroup$
2
$\begingroup$

The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n > 1$) is equal to $n-1$.

It is easier to understand using the fact that minimum vertex covers correspond to the complements of maximum independent vertex sets. In a complete graph $K_n$ the maximum independent set is clearly has only one vertex and so the size of a minimum vertex cover is equal to $|V| - \text{ size of maximum independent vertex set} = n-1$.

$\endgroup$

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.