202402211402

Tags : Combinatorial Optimisation

Primal-Dual Algorithm for general Min-cost Perfect Matching

---

We will show a Primal-Dual algorithm using a combination of Primal-Dual Algorithm for Bipartite Min-cost Perfect Matching and Edmond’s algorithm for general Matching.

Tutte-Berge formula

---

$|M_{\max }|=\underset{U\subseteq V}{\min }\frac{1}{2}(|V|+|U|-o(G\setminus U))$, where $o(S)$ is the number of odd components in $S$. A $U$ that achieves the above equality is called a Tutte-Berge witness.

Factor-critical graphs

---

$G$ is factor-critical if $G$ has no perfect matching but $\forall v\in V$, $G\setminus \{v\}$ has a perfect matching. Claim: If $G$ is factor-critical then:

• $G$ has odd $|V|$,
• $G$ is connected,
• $\varphi$ is the unique Tutte-Berge witness for $G$. (Prove.)

Edmonds-Gallai decomposition

---

For $G=(V,E)$, let $D(G)=\{v\mid \exists \text{ a matching that leaves }v\text{ unmatched}\}$ $A(G)=\{v\mid v\text{ has a neighbour in }D(G)\text{ but }v\notin D(G)\}$ $C(G)=V\setminus (D(G)\cup A(G))$

Then the following hold:

1. $A(G)$ is a Tutte-Berge witness,
2. $C(G)$ is the union of all even components of $G\setminus A(G)$,
3. $D(G)$ is the union of all odd components of $G\setminus A(G)$,
4. Each component in $D(G)$ is factor-critical.

Lemma 1: For any max matching $M$, according to the labelling during Edmond's algorithm,

1. $Even(G,M)=D(G)$
2. $Odd(G,M)=A(G)$
3. $Unlabelled(G,M)=C(G)$

Proof:

1. $v\in Even(G,M)$. So, $v$ has an alternating path $P$ from some $x\in X$, ($X$ is the set of unmatched vertices in $M$). We take the path, and alternate the matching along it to get $M\oplus P$, which is also a max matching, and it leaves $v$ unmatched. Conversely, if $v\in D(G)$, then there exists a matching $M^{\prime }$ that leaves $v$ unmatched. Following the ‘alternating’ path $M\oplus M^{\prime }$, we get that $v$ is an endpoint of an even length alternating path starting from some unmatched vertex.
2. By definition, $v\in Odd(G,M)$ has a neighbour in $Even(G,M)=D(G)$, so $v\in A(G)$, and vice versa. So $A(G)=Odd(G,M)$.

Subtlety: $Even(G,M)$ is the set of all vertices that have an even length alternating path from $X$. So in a blossom, all the vertices will be labelled even.

In Edmond’s algorithm, whenever a vertex can be labelled both even and odd, label it even. So essentially,

3. It follows that $C(G)=Unlabelled(G,M)$.

Every vertex in $A(G)\cup C(G)$ must be matched in every max matching, by definition. Also, $C(G)$ has no edge to $D(G)$. Every vertex in $A(G)$ is matched to $D(G)$. Every vertex in $C(G)$ is matched to some $v\in C(G)$. So all its components are even.

Lemma

Every component $H$ in $D(G)$ has the following property: Either $H$ has one unmatched vertex and $|M\cap \delta (H)|=0$ or $|M\cap \delta (H)|=1$. Moreover, $H$ is factor-critical. Proof: Induction on $|H|$. Base case is fine. Induction step: If $D(G)$ is a bunch of singleton vertices, then we are fine. Otherwise, $H$ contains a blossom, which we shrink and apply induction hypothesis. Thus we get 2 and 4. (This is not a complete argument, but can be completed. We need to show that before/after of shrinking preserves the claims in the lemma.)

To show: $A(G)$ is a Tutte-Berge witness. Or, that $|M|=\frac{1}{2}(|V|+|A(G)|-o(G\setminus A(G)))$. But $|M|=\frac{1}{2}(|V|-|X|)$. To show: $|X|=o(G\setminus A(G))-|A(G)|$. Everything in $C(G)$ can be matched within. Everything in $A(G)$ is matched to something in $D(G)$. So, among all the odd components, i.e. all the components of $D(G)$, exactly $|A(G)|$ many components are matched (to $A(G)$), and the rest have exactly one unmatched vertex each. That is what we wanted to show.

Primal-Dual Algorithm

---

Min-cost perfect matching LP:

$\min \sum _{e\sim E}{c}_e{x}_e$ s.t.

• $\sum _{e\sim v}{x}_e=1\forall v\in V$
• $\sum _{e\in \delta (U)}{x}_e\ge 1\forall U\subseteq V,|U|\text{ odd},|U|\ge 3$
• $x_e\ge 0\forall e\in E$.

Dual variables: $y_U\forall U\subseteq V,|V|\text{ odd}$

$\max \sum _{U\subseteq V,|U|\text{ odd}}$ $\sum _{U\subseteq V,e\in \delta (U),|U|\text{ odd}}{y}_U\le c_e\forall e\in E$ $y_U\ge 0\forall U\subseteq V,|U|\ge 3,|U|\text{ odd}$

Algorithm

---

Idea

The idea is, because the number of dual variables is exponential, we only maintain a small set of “active” variables, and execute the primal-dual algorithm.

$\Omega :$ set of “active” dual variables $\Omega =\{y_v\mid v\in V\}$ (Other $y_v$ are assumed to be $0$.)

Initialise $y_v=0\forall y_v\in \Omega$. (This is feasible for dual.) But $x_e=0\forall e\in E$, so this is infeasible for primal.

Success

$M=\varphi$ $G^{\prime }:$ graph on tight edges $X:$ set of vertices unmatched in $M$ while $M$ is not perfect:

Find an alternating walk $P$ from $u\in X$ to $v\in X$ in $G^{\prime }$. If $P$ is an augmenting path, update $M\leftarrow M\oplus P$, continue; else, we have a blossom $B$. Shrink $B$ to one vertex $b$. Add $y_B$ to $\Omega$, set $y_B=0$.

Note: $b$ is an even vertex.

Continue on $G/B$. If no alternating walk from $X$ to $X$ is found, then $M$ is maximum in $G^{\prime }$, update the dual values:

Find the largest $ϵ$ s.t. $y_U\leftarrow y_U+ϵ$ for even $y_U\in \Omega$, $y_U\leftarrow y_U-ϵ$ for odd $y_U\in \Omega$

If $y_U$ becomes $0$ for $|U|\ge 3$, then unshrink the blossom corresponding to $U$, continue.

Obs.: Some edges which were once tight, can become slack (odd-odd/unlabelled). So number of tight edges is not a measure of progress. The measure of progress is the dual objective value.

Correctness/Optimality

---

Primal objective value $=\sum _{e\in M}{c}_e=\sum _{e\in M}\sum _{U\epsilon \in \delta (U)}{y}_U=$ Dual objective value.

For all edges in $M$, the dual constraint is tight, which gives the second equality. Each non zero $y_U$ appears exactly once, because it is a perfect matching and, for $U=\{v\}$, only one $M$ edge is incident on $v$. For a shrunk blossom, $|M\cap \delta (U)|=1$.

Running time

---

$|\Omega |=n+\frac{n}{2}=O(n)$ $\frac{n}{2}$ augmentations, we will need $m+n$ time to go over all the edges here, and also during the updating values part. Between any two augmentations, $\le \frac{n}{2}$ shrinking operations.

---

References

Linear Programming