In a bipartite graph $(X+Y,E)$, it is possible to find a minimum vertex cover in polynomial time, by Konig's theorem.

Suppose the minimum size is $s$. Is there an efficient algorithm for finding a vertex cover $S$ of size $s$, such that $S\cap X$ has a minimum cardinality?

What I could do so far is to formulate this problem as an ILP where each vertex $u\in X$ has a variable $x_u$ and each vertex $v\in Y$ has a variable $y_v$. Its LP relaxation is:

\begin{align} \text{minimize} && \sum_{u\in X} x_u && \\ \text{subject to} && x_u + y_v \geq 1 && \forall (u,v)\in E \\ && \sum_{u\in X} x_u + \sum_{v\in Y}y_v = s \\ && 1\geq x_{u}\geq 0, 1\geq y_v \geq 0 && \forall u\in X, v\in Y \end{align}

But I do not know how to check whether this ILP has an integer solution.

Is there a better approach to this problem?

  • $\begingroup$ "But I do not know how to check whether this ILP has an integer solution." What did you expect to do with your LP relaxation? Did you want to prove that the relaxation always has an integral solution, such that it exactly solves your original problem? Or did you want to obtain an approximation via LP-rounding? $\endgroup$
    – Discrete lizard
    Jan 20, 2019 at 14:05
  • $\begingroup$ @Discretelizard I was hoping to prove that it has an integer exact solution, just like the original min-vertex-cover in bipartite graphs. $\endgroup$ Jan 20, 2019 at 16:47

2 Answers 2


Dulmage–Mendelsohn decomposition is a powerful tool to capture the structure of the bipartite graph, and it can be found by computing any maximum matching.

Let $G = (V = (A, B), E)$ be a bipartite graph, then $G$ can be partitioned into three parts $(C, H, R)$ and we let :

  1. $C \subseteq V$ is an independent set.
  2. $N(C) = H$.
  3. $G[R]$ has a perfect marching.
  4. $H$ is the intersection of all the minimum vertex covers.
  5. Any maximum-matching in $G$ saturates all vertices in $R \cup U$.

According to the Dulmage–Mendelsohn decomposition, $H$ must be in the solution, so $S = H \cup (A \cap R)$ is a vertex cover with a minimum overlap of $B$ such that $S \cap B = H \cap B \subseteq H$.

We can also solve this problem by using the maximum flow algorithm. Since the Vertex Cover in bipartite problem can be reduced to the minimum cut problem, this problem can be reduced to the minimum cut in the edge-weighted graphs.

Specially, we add a source node $s$ connecting every vertex in $A$ and add a sink node $t$ connecting every vertex in $B$. Suppose that $n = |V|$, the weight of every edge adjacent to the $s$ is $n$, and the weight of every edge adjacent to the $t$ is $n-1$. Besides the weight of the edge in the original graph is large enough such as $n^{2}$. Note that if the size of the minimum vertex cover in $G$ is $k$, we know that the minimum $s$-$t$ cut is in $((k-1)n, kn]$.


Suppose that the minimum VCP size is s.

If $|Y|=s$ then the optimal solution (without solving any problem) is $Y=1$ and $X=0$.

Else, we can solve $min$ $W_uX_u+W_vY_v$ s.t. {$x_u+y_v\ge 1$, $0\le x_u,y_v \le 1$}; i.e. the original VCP relaxation model, where $W_u=1$ and $W_v=1-\epsilon$.

Based on Nemhauser and Trotter Theorem (1975), all extreme optimal solutions have values $V_0=0$, $V_{0.5}=0.5$ or $V_1=1$ for their variables and always we have an optimal solution which is equal to the union of $V_1$ and a subset of $V_{0.5}$.

Therefore, in the optimal solution we have $z^*\approx s$ and between all optimal solutions of original problem with size $s$, the priority of vertex selection of the model is from $Y$.

Then, in optimal solution of the proposed model, select $V_1$ and then solve the problem on $V_{0.5}$. Note that, if $V_0=V_1=\emptyset$ and $V_{0.5}=V$, you can produce an adjacent optimal LP relaxation solution where $V_{0.5}\ne V$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.