# Lecture 9 - LP Relaxation for Matching

###### tags: `Algorithm`

## Problem Definition
+ Matching $M$
+ A set of vertex-disjoint edges
+ Perfect Matching $M$
+ No free vertices
+ Maximum Cardinality Matching (MCM)
+ Maximize $|M|$
+ Maximum Weighted Matching (MWM)
+ Maximize $\sum_{e\in M}w(e)$
+ Example: assignment
+ Task assignment, marriage matching, etc...
## Reduce Bipartite Matching to Flow
+ The residual graph
+ Augmenting path
### Property
+ Alternating paths
+ The edges alternate between $M$ and $E\setminus M$
+ Augmenting paths
+ The alternating paths whose both ends are free vertices
+ One more non-matching edges than matching edges
+ Comparing two matchings
+ $M_1$ is not perfect, $M_2$ is perfect
+ Put them together $M_1\oplus M_2$
+ The **purple** edge: in both
+ The **red** matching is not perfect, so there is an augmenting path between free vertices in it
### Basic Algorithm
:::info
+ Start from the empty matching
+ Repeat
+ Find an augmenting paths
+ Augment along that path (non-matching edges $\iff$ matching edges)
+ Until there is no augmenting paths
:::
## LP for Matching

|$\max \sum_{e\in E}w(e)x(e)$|
|---|
|s.t. $$0\leq x(e)\leq 1, e\in E\\\sum_{e=(u,u')\in E}x(e)\leq 1, u\in V\\x(e)\in\Bbb N, e\in E$$|

### Matching in Bipartite Graph

|Primal|Dual|
|---|---|
|$\max \sum_{e\in E}w(e)x(e)$|$\min\sum_{u\in V}y(u)$|
|s.t. $$0\leq x(e)\leq 1, e\in E\\\sum_{e=(u,u')\in E}x(e)\leq 1, u\in V$$|s.t. $$y(u)+y(v)\geq w(e),e=(u,v)\in E\\y(u)\geq 0,u\in V$$|

### Hungarian algorithm
+ A potential function $y(u)$ on every vertex $u$ satisfying
+ $y(u)+y(v)\geq w(u,v)$ for every edge $(u,v)$
+ $y(u)+y(v)=w(u,v)$ for matching edge $(u,v)$
+ **Tight** edges: $(u,v)$ satisfying $y(u)+y(v)=w(u,v)$
:::info
+ Let $y(u)=N, y(v)=0 (u\in L, v\in R)$
+ Repeat
+ Augment $M$ in $G_y$ (subgraph of tight edges), until there is no augmenting path any more **(Augmentation step)**
+ If $M$ is not perfect, adjust the dual variable $y$ to make more edges tight **(Dual adjustment step)**
+ Until $y(v)=0$ for all free vertex $v$
:::
+ Augmentation step
+ Dual-adjustment step
+ We assign directions to eligible edges
+ Non-matching edges: from $L$ to $R$
+ Matching edges from $R$ to $L$
+ A path between free vertices from $L$ to $R$ $\iff$ augmenting path
+ Find the vertices reachable from free vertices of $L$, call this set $Z$
+ Let $y(u)\leftarrow y(u)-\Delta, u\in L\cap Z$
+ Let $y(v)\leftarrow y(v)+\Delta, v\in R\cap Z$
+ Termination condition
+ If we want a **maximum matching**, then we stop when the free vertices of $L$ have zero $y$-value
+ The $y$-values of **left** free vertices are decreased by the same amount in every step, so they remain equal throughout the algorithm
+ The $y$-values of **right** free vertices are unchanged during the algorithm
+ Now $w(M^*)=\sum_{e\in M^*}w(e)=\sum_{v\in L\cup R}y(v)$
+ For every other perfect $M$, $w(M)=\sum_{e\in M}w(e)\leq\sum_{L\cup R}y(v)$
+ So $w(M^*)\geq w(M)$
+ **So we don’t have the $y(u)\geq 0$ constraint as in the original dual program (That’s only for maximum matching)**
+ Running Time
+ **By Fibonacci heap, every augmenting path takes $O(m+n\log n)$, in total it is $O((m+n\log n)n)$ time**
+ **Hard to be $o(mn)$**
## The *Hopcroft-Karp* Algorithm (1973) for Bipartite Graphs
+ Find a maximal set of shortest augmenting paths in one search
+ Another view of blocking flow algorithm
+ The length of augmenting paths will increase after augmentation
+ **After $n^{1/2}$ iterations, the length of augmenting paths will be at least $n^{1/2}$, so there are at most $n^{1/2}$ free vertices left**
+ For the residual graph $G_f$, find the admissible graph by the distance to $t$
+ $dist(s,t)=D$
+ But it’s easier for matching, since every vertex can only be matched to one edge
+ Find a maximal set of shortest augmenting paths in one search
+ Only takes $O(m)$ time
+ Level graph: 
+ The length of augmenting paths will increase after augmentation
+ After $k$ iterations, the length of augmenting paths will be at least $k$
+ So $|M^*|-|M|≤|M^*|/k\leq n/k$
+ When $k=n^{1/2}$, $|M^*|-|M|≤n^{1/2}$, so we only need to find $n^{1/2}$ augmenting paths
+ So the running time is $O(mn^{1/2})$
## *Gabow and Tarjan*’s approach (1987) for **Bipartite** MWM
### Primal-dual relaxation
+ Original condition
+ $y(u)+y(v)\geq w(u,v)$ (domination)
+ $y(u)+y(v)=w(u,v)$ if $(u,v)\in M$ (tightness)
+ Relaxed condition
+ $y(u)+y(v)\geq w(u,v)-1$ (domination)
+ $y(u)+y(v)=w(u,v)$ if $(u,v)\in M$ (tightness)
+ Then we run the Hungarian search on eligible edges
+ $y(u)+y(v)=w(u,v)-1$ if $(u,v)$ not in $M$
+ $(u,v)\in M$
+ Eligible edges
+ $y(u)+y(v)=w(u,v)-1$ if $(u,v)$ not in $M$
+ All the matching edges
+ After augmentation, to make matching edges remain tightness, we **add $1$** to the $R$-side vertex of every new matching edges
+ So other edges associated with these vertices will not be eligible any more
+ Thus, if we perform it on a **maximal set** of augmenting paths, there will be no augmenting paths any more
+ One search only takes $O(m)$ time
+ Similar to the distance-increasing in *Hopcroft-Karp* algorithm
+ Until we get a perfect matchin
+ We get $M$, here $M^*$ is the real maximum weight **perfect** matching
+ $w(M)=\sum_{e\in M}w(e)=\sum_{v\in L\cup R}y(v)$
+ $w(M^*)=\sum_{e\in M^*}w(e)\leq\sum_{v\in L\cup R}y(v)+|M^*|=w(M)+n$

### Integer Edge Weights
+ Integer edge weights $[1,...,W]$
+ Scaling on the edge weights
+ Multiples of $W/2,W/4,…,1/n,1/(2n)$
+ $\epsilon =1$
+ Suppose a weight: $11001_2$ (WLOG let $n$ be the power of $2$)
+ $1, 11, 110, 1100, 11001, 110010, 1100100, 11001000$
+ So finally $w’(e)=2n\times w(e)$, and $w’(M^*)≤w’(M)+n$
+ $w(M^*)\leq w(M)+1/2$, ($M^*$ is the real MWPM)
+ $w(M^*)=w(M)$
+ So there are $\log(nW)$ scaling iterations
+ Thus the total number of scaling iterations is $O(\log(nW))$
#### Theorem: Every iteration takes $O(mn^{1/2})$ time
+ At the beginning of each iteration, suppose this is the perfect matching we get in the last iteration
+ New weights: $w’(e)=2w(e)$ or $2w(e)+1$
+ To maintain the dominance condition, we let: $y’(u)\leftarrow 2y(u)+2$
+ **Now $y’(u)+y’(v)\geq w’(u,v)$ for all edges $(u,v)$**
+ $y'(u)+y'(v)=2(y(u)+y(v))+4\geq 2w(u,v)+2>w'(u,v)$
+ Old matching edge: $y’(u)+y’(v)\leq w’(u,v)+4$
+ Make all edges nonmatching edges, start the search again
+ Define new weights $w(u,v)\leftarrow w’(u,v)-y’(u)-y’(v)$
+ **All edges are $\leq 0$**
+ **Maximum perfect matching: $\geq -4n$** (by the old matching)
+ We start the Hungarian search for $y(u)=0$ for all vertex $u$
+ Then if the $y$-value of left free vertices reaches $–k$
+ The current matching: $M$
+ The old perfect matching: $M^*$
+ Number of left free vertices: $F$
+ $\sum_{v\in L\cup R}y(v)=w(M)-kF\leq -kF$
+ $-4n\leq w(M^*)\leq\sum_{v\in L\cup R}y(v)+n\leq -kF+n$
+ Thus $kF\leq O(n)$
+ So after $n^{1/2}$ steps, there are only $O(n^{1/2})$ free vertices left, we can augment in $O(n^{1/2})$ iterations
### Summary
+ MWPM for bipartite graph in $O(mn^{1/2}\log(nW))$ time
+ $\log(nW)$ scales
+ In each scale there are $n^{1/2}$ steps to make $k=-n^{1/2}$, then there are $O(n^{1/2})$ free vertices left
+ Why not $O((m+n\log n)n^{1/2}\log(nW))$ by Fibonacci heap?
+ **In fact, the $y$-values are integer in $[0,...,n]$, so bucket sort is enough**
## Reduction between MWM and MWPM
### MWM $\Rightarrow$ MWPM
+ Duplicate $G$, we have $G_1=(L_1,R_1)$ and $G_2=(L_2,R_2)$
+ Link the two copies of every vertex of G by an edge with weight zero
+ Still a bipartite graph: one side $L_1\cup R_2$, the other side $L_2\cup R_1$
+ The number of vertices and edges are still $O(n)$ and $O(m)$, respectively, and weights do not change
### MWPM $\Rightarrow$ MWM
+ If the weights are in $[0,...,W]$, add $nW$ to the weight of every edge, and get a new graph $G’$
+ The weight of a matching of $k$ edges in $G’$ is $\leq k(n+1)W$ (when $k\leq n-1$, $k(n+1)W<n^2W$)
+ The weight of a perfect matching in $G’$ is $\geq n^2W$
+ So the maximum matching in $G’$ must be a perfect matching
+ **Weights becomes larger**
### Summary
+ [*Gabow & Tarjan 1987*] MWPM for bipartite graph in $O(mn^{1/2}\log(nW))$ time
+ [*Duan & Su 2012*] MWM for bipartite graph in $O(mn^{1/2}\log W)$ time
## Approximate Matching
+ In ***Hopcroft-Karp*** algorithm, after $k$ iterations, the length of augmenting paths will be at least $k$
+ If we compare the current matching $M$ and the maximum matching $M^*$, we can get $|M^*|-|M|$ disjoint augmenting paths
+ So $|M^*|-|M|\leq |M*|/k$
+ And $|M|\geq |M^*|-|M^*|/k=(1-1/k)|M^*|$
+ So we can get a $(1-1/k)$-approximate matching in $O(km)$ time
### Relaxed conditions
+ Throughout the algorithm
+ $y(u)+y(v)\geq w(u,v)-1/k$ (domination)
+ $y(u)+y(v)=w(u,v)$ if $(u,v)\in M$ (tightness)
+ Then we run the Hungarian search on eligible edges
+ $y(u)+y(v)=w(u,v)-1/k$ if $(u,v)$ not in $M$
+ $(u,v)\in M$
+ Eligible edges
+ $y(u)+y(v)=w(u,v)-1/k$ if $(u,v)$ not in $M$
+ All the matching edges
+ After augmentation, to make matching edges remain tightness, we add $1/k$ to the $R$-side vertex of every new matching edges
+ So other edges associated with these vertices will not be eligible any more
+ Thus, if we perform it on a maximal set of augmenting paths, there will be no augmenting paths any more
+ One search only takes $O(m)$ time
+ Similar to the distance-increasing in *Hopcroft-Karp* algorithm
+ So other edges associated with these vertices will not be eligible any more
+ Thus, if we perform it on a maximal set of augmenting paths, there will be no augmenting paths any more
+ During dual-adjustment, the $y$-value of free vertices on the left side will be reduced by $1/k$
+ Until $y$-value of free vertices become all-zero
+ We get $M^*$, here $M$ is any other matching
+ Now: $w(M^*)=\sum_{e\in M^*}w(e)=\sum_{v\in L\cup R}y(v)$
+ And: $w(M)=\sum_{e\in M}w(e)\leq\sum_{v\in L\cup R}y(v)+w(M)/k\leq w(M^*)+w(M)/k$
+ So after $kW$ dual-adjustments we can get a $(1-1/k)$-approximate maximum weighted matching
#### Summary
+ Primal-dual relaxation on the linear programming formation of MWM
+ Converge more quickly
+ Make the relaxation dynamic: tighten the relaxation amount when the dual variable decreases
+ The relaxation on matching edges is proportional to their edge weights
+ In FOCS 2010 paper, we use another scaling approach which uses this $O(mkW)$ algorithm as a subroutine
+ Now we can do the scaling simply on this algorithm
### Reduce to $O(\epsilon^{-1}m\log W)$ time
+ We have $\log W$ phases based on the y-values of the free vertices
+ $W$ to $W/2$, $W/2$ to $W/4$,...
+ The relaxation amount decreases by one half ($ε_{i+1}=ε_i/2$)
+ When we get into a new phase $i+1$, and we increase the yvalues of all vertices by $ε_{i+1}/2$
+ Originally we have
+ $y(u)+y(v)\geq w(e)-ε_1$
+ $y(u)+y(v)=w(e)$ if $e=(u,v)$ is a matching edge
+ After adding $ε_2/2$ to every $y(u)$, we have
+ $y(u)+y(v)\geq w(e)-ε_1+ε_2=w(e)-ε_2$
+ $y(u)+y(v)=w(e)+ε_2$
+ If $e$ is a matching edge found in the first phase
+ $y(u)+y(v)=w(e)$
+ If $e$ is a matching edge found in the second phase
+ So for the matching edge of weights between $W/2^{i-1}...W/2^i$ found in this algorithm, we have
+ $y(u)+y(v)\leq w(e)+ε_i/2+ε_{i+1}/2+ε_{i+2}/2+...\leq w(e)+ε_i =w(e)+ε_1/2^{i-1}$
+ So the approximation ratio is still proportional to the edge weights
+ Also, every phase needs $O(ε^{-1}m)$ time, so the total time is $O(ε^{-1} m\log W)$
### Reduce to $O(\epsilon^{-1}m\log \epsilon^{-1})$ time
+ For every edge $e$, we only need to consider it in $\log ε^{-1}$ phases
+ After that, $yz(e)$ can only change for $\epsilon w(e)$
+ **Easy to extend to general graphs**