4
$\begingroup$

Disclaimer: This is a homework question.

I would like to reduce vertex cover problem to the following problem:

$$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$

I have divided the problem into three parts:

  • $k = n/2$: This case is trivial.
  • $k > n/2$: Yes in vertex cover problem does not necessarily mean yes in $L$.
  • $k < n/2$: No in vertex cover problem does not necessarily mean no in $L$.

I know that I need to change graph $G$ into $G'$ somehow to map results of VC to $L$.

Any advice on how to do so is appreciated.

Improve this question
$\endgroup$
2
  • $\begingroup$ After NT reduction (it’s polynomial), a graph has a vertex cover of size at least $\frac{n}{2}$. $\endgroup$
    – Eugene
    Commented Apr 9, 2018 at 21:50
  • $\begingroup$ What's $k$? The target size in the Vertex Cover problem? $\endgroup$
    – David Richerby
    Commented Apr 10, 2018 at 14:59

3 Answers 3

Reset to default
2
$\begingroup$

For $k<n/2$, add an isolated complete graph with $n-2k+2$ vertices (note it takes at least $m=n-2k+1$ vertices to cover this complete graph). Now there is a vertex cover of size $(n+(n-2k+2))/2=n-k+1$ in the new graph iff there is a vertex cover of size $(n-k+1)-m=k$ in the old graph.

For $k>n/2$, add $2k-n$ isolated vertices. Now there is a vertex cover of size $(n+(2k-n))/2=k$ in the new graph iff there is a vertex cover of size $k$ in the old graph.

Improve this answer
$\endgroup$
0
$\begingroup$

For k < n/2, add enough vertices with a single edge out of them (pointing back at themselves) such that the size of the new vertex cover is half the size of the new graph.

For k > n/2, add enough vertices connected to an arbitrary vertex already in the vertex cover such that the size of the original vertex cover is half the size of the new graph.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "an arbitrary vertex already in the vertex cover" -- we don't know which vertices make up a vertex cover yet. Just adding isolated vertices works. Also, if self-edges are disallowed, then for the k < n/2 case you can add triangles. 2 out of 3 vertices in each triangle must be chosen, so it's always possible to add enough triangles to bring the total k required up to n/2. $\endgroup$
    – j_random_hacker
    Commented Jan 10, 2018 at 12:04
-2
$\begingroup$

This question was answered in the following video (By me): https://www.youtube.com/watch?v=rKNasOecTu0

In a nut-shell, the key here is to modify the graph in such a way it wouldn't be profitable to select vertices from the modified graph, and by finding a full vertex cover in the original graph, you could get a half vertex cover in the modified graph.

Hope that helps :-)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Can you edit this answer to disclose your connection to the creator of that video? See cs.stackexchange.com/help/promotion. Note that we discourage answers that consist solely or primarily of an external link. We want to create useful new content, not just be a link farm; and if the link stops working, we need answers to remain useful. Thank you! $\endgroup$
    – D.W. ♦
    Commented Apr 26, 2020 at 20:18
  • 1
    $\begingroup$ Hi D.W, the creator of the video is myself. I stumbled upon this question a few days ago, and since I solved it, I made a video about it, to help myself and computer science students :-) Is there a way to embed the video to my response, rather than putting a link? $\endgroup$
    – CUCUMBER
    Commented Apr 27, 2020 at 1:29

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.