2
$\begingroup$

Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following proof, based on primal-dual linear program, is valid. This is mainly an exercise in understanding this primal-dual concept.

Step 1: define an LP for the maximum matching. For every edge $(u,v)\in E$, define a variable $z_{uv}$ whose value is 1 if the edge is in the matching. The LP is:

\begin{align} \text{maximize} && \sum_{(u,v)\in E} z_{uv} && \\ \text{subject to} && \sum_{v\in Y} z_{uv} \leq 1 && \forall u\in X \\ && \sum_{u\in X} z_{uv} \leq 1 && \forall v\in Y \\ && z_{uv}\geq 0 && \forall (u,v)\in E \end{align}

Step 2. Create the dual LP using the recipe:

  • Each primal constraint becomes a dual variable - so there is a variable $x_u$ for each $u\in X$ and a variable $y_v$ for each $v\in Y$.
  • The sign of each dual variable is opposite to the sign of its primal constraint - so $x_u\geq 0, y_v\geq 0$.
  • The dual objective is minimization, where the coefficient of each dual variable is the number on the right-hand side of its primal constraint - in this case it is always 1. So the objective is "minimize $\sum x_u + \sum y_v$".
  • Each primal variable becomes a dual constraint. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. In this case, the coefficient of the dual variable of a node $i$, in the dual constraint of the edge $(j,k)$, should be 1 iff $i=j$ or $i=k$.
  • The sign of each dual constraint is the sign of its primal variable.
  • All in all, the dual LP is:

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

The dual LP finds a minimum vertex cover - it minimizes the number of vertices under the constraint that for each edge, at least one of its endpoints is in the cover.

My question is: is this proof valid?

The main thing I am not sure at is that the LP allows fractional variables, while the original problems are integral. What argument should be added to handle this issue?

$\endgroup$
2
$\begingroup$

Your proof is missing a crucial ingredient, namely that for bipartite graphs, your LPs have the same objective value as the corresponding IPs. This is not true in general (otherwise vertex cover would be in P). You can see a proof for maximum matching in lecture notes of Meena Mahajan, and a proof for both in lecture notes of A. A. Ahmadi.

$\endgroup$
  • $\begingroup$ Ah, I see. I proved that the maximum fractional matching equals the minimum fractional covering, but in a general graph, the maximum integral matching might be smaller and the minimum integral covering might be higher. Thanks $\endgroup$ – Erel Segal-Halevi Jan 18 at 13:45

Your Answer

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

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