202402021402

Tags : Combinatorial Optimisation

LP algorithm for general Perfect Matching

---

$G=(V,E)$. $|V|=n$ (even), $|E|=m$. $\delta (v)=$ set of edges incident on $v$, $\delta (S)=$ set of edges with exactly one endpoint in $S$.

LP:

• $\sum _{e\in \delta (v)}{x}_e=1\forall v\in V$
• $\sum _{e\in \delta (S)}{x}_e\ge 1\forall S\subseteq V,|S|\text{ is odd},3\le |S|<|V|-1$
• $x_e\ge 0\forall e\in E$

The second constraint here says that for every odd subset, not everything is matched within itself, like in the triangle $\frac{1}{2},\frac{1}{2},\frac{1}{2}$ case. We require at least one edge in the boundary of each odd set to be in the matching (and relax integrality).

Let $P_G$ be the polytope of graph $G$ given by the above LP.

Obs.:

1. Any $0/1$ point in $P_G$ is a perfect matching of $G$.
2. All perfect matchings of $G$ are in $P$.

---

Theorem: Vertices of $P$ are perfect matchings of $G$, i.e. $P=$ convex hull of the perfect matchings.

Proof: Suppose not. There is a graph $G$, and an extreme point $\hat{x}$ of the polytope $P_G$ which is not a perfect matching of $G$. Among all such counterexamples, let $G$ be one with minimum $|V|+|E|$.

Claim 1: $\forall e\in E0<\widehat{x_e}<1$.

1. If ${\hat{x}}_{e_i}=0$, then $G\setminus \{e_i\}$ is a smaller counterexample.
2. If ${\hat{x}}_{e_i}=1,e_i=(u,v)$, then $G\setminus \{u,v\}$ is a smaller counterexample.

(Check that the new $\hat{x}\setminus e_i$ is still an extreme point of the new polytope, in 2. as well.)

Obs.:

1. $G$ has no degree $1$ vertex.
2. $G$ can’t have all vertices of degree $2$, because then $G$ would just be a bunch of vertex disjoint cycles. If all the cycles are even, we get a perfect bipartite matching, and if any of them are odd, then there does not exist a perfect matching at all and the polytope itself is empty!

So $G$ has a vertex of degree $>2$. Which means $|E|>|V|$, or $m>n$.

$\hat{x}\in {\mathbb{R}}^m$ is a vertex (extreme point) of $P_G$, so $m$ constraints must be tight at $\hat{x}$. There must be at least one of the second type constraints which is tight at $\hat{x}$. Say it is due to the set $U\subseteq V$.

Goal: To show $\hat{y},\hat{z}$ s.t. $\hat{x}=\lambda \hat{y}+(1-\lambda )\hat{z}$.

We know that ${\hat{x}}_{e_1}+\cdots +{\hat{x}}_{e_h}=1$, where $e_1,\dots ,e_h$ are the edges that go from $U$ to $V\setminus U=\bar{U}$. Shrink $U$ to a new vertex $u$ to get a smaller graph $G^{\prime }$, and similarly $\bar{U}$ to $\bar{u}$ to get $G^{\prime \prime }$.

Obs.:

1. A perfect matching $M$ of $G$ is a valid perfect matching $M^{\prime }$ of $G^{\prime }$, and $M^{\prime \prime }$ of $G^{\prime \prime }$ iff $|M\cap \{e_1,\dots ,e_h\}|=1$.
2. If $M^{\prime }$ and $M^{\prime \prime }$ are perfect matchings of $G^{\prime }$, $G^{\prime \prime }$ respectively, using the same edge among $e_1,\dots ,e_h$, then $M^{\prime }\cup M^{\prime \prime }$ is a perfect matching for $G$.

Since $G^{\prime }$ and $G^{\prime \prime }$ are smaller than $G$, they obey the theorem, i.e. their polytopes are integral. ${\hat{x}}_{G^{\prime }}=\sum _{i=1}^{k_1}{\alpha }_i{M}_i^{\prime }$. ${\hat{x}}_{G^{\prime \prime }}=\sum _{j=1}^{k_2}{\beta }_i{M}_j^{\prime \prime }$. $\sum {\alpha }_i=\sum {\beta }_j=1$, $0\le {\alpha }_i\le 1$, $0\le {\beta }_i\le 1$.

${\hat{x}}_{e_1}=\sum _{i:e_1\in M_i^{\prime }}{\alpha }_i=\sum _{j:e_1\in M_j^{\prime \prime }}{\beta }_j$

For each edge $e_k$, take $\sum _{i:e_k\in M_i^{\prime }}{\alpha }_i\sum _{j:e_k\in M_j^{\prime \prime }}{\beta }_j(M_i^{\prime }\cup M_j^{\prime \prime })$ , scale it by the right thing to write ${\hat{x}}_G$ as the convex combination of these “union matchings”.

---

References