Vertex Cover In Bipartite Graph

Vertex Cover Problem (VCP):  Given a graph $G=(V, E)$ , Find minimum number of vertices that cover all the edges i.e., a set $V' \subseteq V$ of  such that $\left|{V'}\right|$ is minimum and for every edge at least one end point belongs to $V'$.

Weighted Vertex Cover Problem (WVCP): Given a graph $G=(V, E)$ and a cost function $\omega : V \rightarrow R^+$, Find minimum weight vertex set that cover all the edges i.e., a set $V' \subseteq V$ of  such that $\omega(V') = \sum_{v \in V'} \omega(v)$ is minimum and for every edge at least one end point belongs to $V'$.

Bipartite Graph: A Graph whose vertex set is partitioned into two sets $A$ and $B$  where each edge joins a vertex in $A$ to a vertex in  $B$.

Integer Program for VCP: For each  vertex $v \in V$, take a variable $x_v$. Now define $x_v = 1$ if vertex $v$ is in our solution and  $x_v = 0$ otherwise. Therefore the integer program (IP) for  VCP  is as follows:

min $\sum_{v \in V}x_v$

$s.t. x_u + x_v \geq 1$ for all $e = (u,v) \in E$

$x_v \in \{0, 1\}$ for all $v \in V$

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.