Vertex Cover degree problem

Question

So Vertex cover (VC):

Instance: a graph $G$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$?

We will now define a version of this problem in which we assume that the degree of each node in a given graph is $2$:

2-vertex cover (2-VC). Instance: a graph $G$ in which each node has degree $2$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$?

For the following, decide whether the answer is “Yes”, “No” or “Unknown because it would resolve the $P =? NP$ question.” Prove your claim.

(a) Is $2-VC ≤_P VC$?

(b) Is $VC ≤_P 2-VC$?

and

a second question here

http://pastie.org/private/ljxo6aqg3a9troxpnpxriq

These questions ares really nagging me because i'm not sure what is meant by the phrase degree 2. Is this the cost of the vertex?

Also i'm aware of the general proof of vertex cover that shows how basically we use the compliment of the independent sets to show a vertex cover.

I'm in the middle of revising for exams and these are eluding me, anyone have any suggestions?

UPDATE: I think 1a) is basically just plugging in a 2 degree VC into a graph that can solve the problem in one step and then deriving the answer through that with a cast.

Answer 1

First Question

You need two observations

1. The problem 2-VC is in ${\sf P}$. This can be shown as follows. In a graph, where every vertex has degree $2$, every connected component is a cycle. You can decide for every component (cycle) separately, how many vertices you need to cover it. In particular, if the cycle has $m$ edges the minimum vertex cover has size $\lceil m/2 \rceil$. Notice that every language in $X\in {\sf P}-\{\emptyset,\Sigma^*\}$ is also ${\sf P}$-complete, since for any $L\in {\sf P}$, you can map easily $w\in L \iff f(w)\in X$ with help of the decision algorithm for $L$.

2. VC is a generalization of 2-VC. Hence any algortihm for VC, can answer 2-VC requests. Thus you can take the identity as reduction and you get 2-VC$\le_p$VC. This is what you observed in Update 1.

Now you can argue as follows. (a) holds independent of whether ${\sf P}={\sf NP}$ or not. If ${\sf P}={\sf NP}$, then VC is in ${\sf P}$ and since 2-VC is ${\sf P}$-complete (b) holds. On the other hand, (b) implies that 2-VC is ${\sf NP}$-complete and in ${\sf P}$, and hence ${\sf P}={\sf NP}$ has to hold (thus it is false when ${\sf P}\ne{\sf NP}$).

Second Question

You can define a reduction from 3-SAT to ADV-3SAT as follows. Let $\psi$ be the 3-SAT formula you want to transform into a ADV-3SAT formula $\psi'$. Take every variable $x_i$, and replace it by a new variable $x_i^j$, for $j$ being the $j$th occurrence of $x_i$ in $\psi$. As a next step you add clauses to assure that all the copies of a variable are either all true or all false. In other words, you want to ensure that $x_i^{j_1} \iff x_i^{j_2}$. In CNF you get $(x_i^{j_1} \lor \overline{x_i^{j_2}}) \land (x_i^{j_2} \lor \overline{x_i^{j_1}})$. Add this for every triplet $i,j_1,j_2$ to get $\psi'$. Notice that $|\psi|$ and $|\psi'|$ are polynomially realated. By construction $\psi$ is true, iff $\psi'$ is true, and hence $\psi$ is satisfiable, iff $\psi'$ is satisfiable.

Answer 2

For the first question - If every vertex has 2 edges incident on it, then the graph is a union of disjoint cycles. Can you find a minimum vertex cover for a single cycle? How do vertex covers of disjoint cycles affect each other? What does that mean about how easy it is to solve 2-VC?

For the second question - Take an instance of 3-SAT. If each variable shows up in at most 3 clauses, we're done. If a variable shows up in more than 3 clauses, can you 'split' the variable into multiple new variables so that each of the new variables shows up in at most 3 clauses, the new variables are linked in the sense that they are all true or all false, and their truth/falsehood is a proxy for the original variable?