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?
