1
$\begingroup$

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?

$\endgroup$
  • $\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 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$ – Erel Segal-Halevi Jan 20 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.