**Vertex Cover Problem (VCP):** Given a graph , Find minimum number of vertices that cover all the edges i.e., a set of such that is minimum and for every edge at least one end point belongs to .

**Weighted Vertex Cover Problem (WVCP): **Given a graph and a cost function , Find minimum weight vertex set that cover all the edges i.e., a set of such that is minimum and for every edge at least one end point belongs to .

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

**Integer Program for VCP: **For each vertex , take a variable . Now define if vertex is in our solution and otherwise. Therefore the integer program (IP) for VCP is as follows:

min

for all

for all

Pingback: Local Limits | Eventually Almost Everywhere