Show that problem is solvable in polynomial time.

Question

Input: Graph $G=(V,E)$, sets $V_1,V_2,\ldots,V_k\in V$.

Question: Is there a VertexCov of G such that $|C\cap V_i|\leq 1,\ i=1,2,\ldots,k$?

I have to show that this problem is solvable in polynomial time. Since $|C\cap V_i|\leq 1$ that means if $(\forall v\in C) (c\in V_i \vee c\notin V_i)$, so I am thinking of how to model this via 2-SAT since that is polynomialy solvable but can't get to the solution. Any help or hits on how to proceed?

Answer 1

For every $v \in V$, let $x_v$ be true if and only if $v$ is in the vertex cover.

For every edge $(u,v) \in E$, a vertex cover satisfies $(x_u \vee x_v)$. Moreover for $V \in \{V_1, \ldots, V_k\}$, $|C \cap V| \leq 1$ implies

$$ \bigwedge_{u \in V} \bigwedge_{v \in V, v \neq u} (\neg x_u \vee \neg x_v) \enspace. $$

A model for this set of clauses, if it exists, gives the desired vertex cover $C$. Since all clauses have two literals, and the number of clauses is bounded by a polynomial in $n$ (the number of vertices) and $k$, the problem is solvable in polynomial time.