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.

  • $\begingroup$ 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$. $\endgroup$ – Dibyayan Sep 30 '14 at 5:50
  • $\begingroup$ @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. $\endgroup$ – R B Sep 30 '14 at 6:33

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.