Advanced Algorithms UE 1

by Maarten Behn
Group 5

Exercise 1.1 (Algorithm for maximum weight bipartite matching)

For the weighted bipartite graph given below and for each $k\in \{1,2,3,4,5\}$, compute a maximum weight matching $M_k$ of cardinality $k$.

Exercise 1.2 (Improved running time for maximum weight bipartite matching)

Prove the following theorem from the lecture:
We can compute a maximum-weight matching in a bipartite graph in time $O(n^{\prime }\cdot (|E|+|V|log(|V|)))$, where $n^{\prime }$ is the minimum size of a maximum-weight matching.

Given

• bipartite graph $G=(V,E,c)$
• directed Graph $D_M$
• set of exposed vertecies $R_M$
• the maximum weight matching $M$ with no $s-R_M$ path in $D_M$ with negative length

Task

Let $k:=|M|$ be the cardinality of $M$
Let $M_n$ be a maximum matching in $G$ of cardinality $n\in k..|\frac{V}{2}|$

proof that $c(M_n)\le c(M)$

Proof by induction over n

Start $n=k$

$M=M_n$ → $c(M)=c(M_n)$
($M$ and $M_k$ are equal so this is obviously true) tho

Step $n^{\prime }=n+1$

Let $P$ be a $s-R_{M_n}$ path in $D_{M_n}$
Let $P^{\prime }$ be the shortest $s-R_{M_n}$ path in $D_{M_n}$
Let $c(P):=\sum _{e\in P}c(e)$ (The sum of all weights of a path also refered to as the length.)

Observation

$c(M_{n^{\prime }})=c(M_n)-c(P^{\prime })$ (The weight of the matching always increases by the negative weight of the shortest path. I have not proofen this futher as it seems obvious. I hope this is fine. I did not really know how formal the proof should be.)

$c(M_{n^{\prime }})\le c(M_n)$ because $c(P)\ge 0$

Exercise 1.3 (Algorithm for the assignment problem)

Prove the following theorem from the lecture:
We can compute a minimum-weight perfect matching in a bipartite graph in time $O(|V|\cdot (|E|+|V|log(|V|)))$.

Given

• bipartite graph $G=(V,E,c)$

Task

1. Show how to perform the minimum-weight perfect matching in a bipartite graph
2. Proof that it has a runtime of $O(|V|\cdot (|E|+|V|log(|V|)))$

1. Show by reduction to maximum weight matching

Let $C:=max(c(e))\forall e\in E$
Let $c^{\prime }(e):=C-c(e)$
Let $G^{\prime }:=(V,E,c^{\prime })$
Perform the first and second step of maximum weight matching on $G^{\prime }$.
Let $S$ be the set of computed matchings from the second step.
Let $k:=\frac{|V|}{2}$
Let $M$ be the matching in $S$ with cardinality $k$.
$M$ is the minimum-weight perfect matching in $G$.

Proof: $M$ exists in $S$

A maximum weight matching of $G$ could be of cardinality $k$ therefore the $S$ must contain $M$.

Proof: $M$ is a perfekt matching

$M$ is of cardinality $k$.

Proof: $M$ is a minimum-weight matching

Observation

$\sum _{e\in M}{c}^{\prime }(e)=C\cdot |M|-\sum _{e\in M}c(e)$

$\sum _{e\in M}c(e)$ is the maximum weigth of all perfect matchings.
If the maximum value is subtracted from a constant value the resulting value is the minimum. Because both sums are over the same matching,
$\sum _{e\in M}{c}^{\prime }(e)$ is the minimum weight of all perfect matchings.
→ M is a minimum-weight matching

2. Proof that its runtime is $O(|V|\cdot (|E|+|V|log(|V|)))$

Steps	Runtime
Let $C:=max(c(e))\forall e\in E$	$O(E)$
Perform maximum weight matching	$O(\Vert V\Vert \cdot (\Vert E\Vert +\Vert V\Vert log(\Vert V\Vert )))$

All other steps have a runtime of $O(1)$.

$O(|V|\cdot (|E|+|V|log(|V|))+E)$
$\Rightarrow O((|V|+1)\cdot (|E|+|V|log(|V|))$
$\Rightarrow O((|V|)\cdot (|E|+|V|log(|V|))$

Sources

The idea for $C$ I got from here:
https://www.cse.iitd.ac.in/~naveen/courses/CSL851/lec4.pdf (10.4.25, 22:09)