# Minimum vertex cover for bipartite graphs

I know that it is possible to calculate the minimum vertex cover of a bipartite graph,

However, i want that the minimum vertex cover which contains vertices from only one partite set, which will be given as input,

Any ideas how to design the algorithm ?

Note that the answer to the above question might contain more vertex than the minimum vertex cover but all those sets would contain vertices from both partite !

If $G(V,E)$ is the original graph with $V=A\cup B$ the set of vertices partitioned in two disjoint sets $A$ and $B$. The general VC problem: we are looking for a subset $S$, $S\subseteq V$ such that it 'covers' every edge in $E$. If I understand correctly, in this variation we require $S\subseteq A$ or $S\subseteq B$.
Then, assuming all of the nodes has a positive degree, use $S=A$ or $S=B$, i.e. the entire set $B$ or $A$. Without loss of generality let us assume $S=A$ is the vertex cover we are looking for. For a contradiction, there is some $x\in A$ that x is not in the VC, so $S=A\setminus\{x\}$ and x has at least one edge: $x\in A,v\in B, (x,v)\in E$, then the edge $(x,v)$ is not covered by S and since we cannot pick vertex $v$ for the VC, $x$ must be in $S$ or otherwise $S$ will not be a vertex cover. So choose the smallest of the two.
• even though the edge $(x,v)$ is not covered, $v$ can be covered if there exists $y$ in A and in $S$ such that $(y,v) \in E$. – Dibyayan Sep 30 '14 at 5:50
• @Dibyayan - in vertex cover you need to cover all edges. If you're looking for a vertex-subset of $V$ such that every other vertex has a neighbor in $S$, then this is called "Dominating Set", which is known to be NP-Hard for bipartite graphs. – R B Sep 30 '14 at 6:33