<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-09-30T05:50:55.550Z
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
CC BY-SA 3.0
2014-09-30T06:33:19.060Z
@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
CC BY-SA 3.0
2014-09-29T10:59:16.183Z
2014-09-29T11:46:58.167Z
2014-09-29T11:46:58.167Z
Harry
<p>I know that it is possible to calculate the minimum vertex cover of a bipartite graph,</p>

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

<p>Any ideas how to design the algorithm ?</p>

<p>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 !</p>

<graph-theory><graph-algorithms>
Minimum vertex cover for bipartite graphs
Dibyayan
# Minimum vertex cover for bipartite graphs

(Asked by: username_0 on 2014-09-29)

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 !

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2014-09-29. Score: 0 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$.  
> **username_2**: @username_0 - 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.  

---

