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.

$\endgroup$
2
  • $\begingroup$ After NT reduction (it’s polynomial), a graph has a vertex cover of size at least $\frac{n}{2}$. $\endgroup$ – Eugene Apr 9 '18 at 21:50
  • $\begingroup$ What's $k$? The target size in the Vertex Cover problem? $\endgroup$ – David Richerby Apr 10 '18 at 14:59
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.

$\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.

$\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 Jan 10 '18 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 :-)

$\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. Apr 26 '20 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 Apr 27 '20 at 1:29

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.