Advanced Algorithms UE 2

by Maarten Behn
Group 5

Exercise 2.1

Compute a maximum matching of the graph given below.
Choose the shortest paths in DM such that you apply at least 3 times the ’shrink’ operation of the algorithm.

Exercise 2.2

Consider the following simple algorithm to compute a matching in a given graph $G$.
We fix some $k\in N,k\ge 1$.

1. Let $M$ be the current matching.
2. If there is a set of $k$ edges $M^{\prime }\subseteq M$ and a set of $k+1$ edges $F\subseteq E\backslash M$ such that $(M\backslash M^{\prime })\cup F$ is a matching, update $M$ to $(M\backslash M^{\prime })\cup F$ . Repeat.
   Show the following:

a) The running time of the algorithm is $O(|E^{2(k+1)})$.

Given:

Let $G=(V,E)$
Let $M$ be a matching in $G$
Let $k\ge 1$

The Algorithm written in steps:

Go over all possible $M^{\prime }\subset M:|M^{\prime }|=k$
There are $\left(\frac{|M|}{k}\right)$ different $M^{\prime }$.
Go over all possible $F\subseteq E\backslash M:|F|=k+1$
There are $\left(\frac{|E\backslash M|}{k+1}\right)$ different $F$.
Check if $(M\backslash M^{\prime })\cup F$ is a matching
This takes $k+1$ operations
because we need to check if every new edge has no neigbor in the matching.

$O\left(\left(\frac{|M|}{k}\right)\cdot \left(\frac{|E\backslash M|}{k+1}\right)\cdot (k+1)\right)$
$\Rightarrow O\left(|E{|}^k\cdot |E{|}^{k+1}\cdot (k+1)\right)$ because $\left(\frac{|M|}{k}\right)\le |E{|}^k$, $\left(\frac{|E\backslash M|}{k+1}\right)\le |E{|}^{k+1}$
$\Rightarrow O\left(|E{|}^{2(k+1)}\cdot (k+1)\right)$ because $|E{|}^{k+1}\ge |E{|}^k$
$\Rightarrow O\left(|E{|}^{2(k+1)}\right)$ because $k+1\le |E{|}^{2(k+1)}$

b) Let M be the matching output by the algorithm and let $M^{\ast }$ be a maximum matching in G.

Show that $|M|\ge \frac{k+1}{k+2}|M^{\ast }|$

Lets take $M△M^{\ast }$
Each connected component is either:

• a cycle: the number of edges from $M$ and $M^{\ast }$ are equal.
• a path: the number differs by 1 if it starts and ends with an edge from $M^{\ast }$, it has one more edge from $M^{\ast }$ than from $M$.

Since no local improvement of exchanging $k$ edges from $M$ with $k+1$ edges from $E\setminus M$ is possible,
the number of $M^{\ast }$ edges cannot exceed the number of $M$ edges by more than a factor of $\frac{k+1}{k}$.

$(k+1)(|M^{\ast }|-|M|)\le k|M|$
$\Rightarrow (k+1)|M^{\ast }|\le (k+2)|M|$
$\Rightarrow |M|\ge \frac{k+1}{k+2}|M^{\ast }|$

Exercise 2.3

Consider the game Slither by W. Anderson.
Given an undirected, simple connected graph $G=(V,E)$, two players choose in turns an edge e with the following rule:
$e$ was not yet chosen and the set of up to now chosen edges (including $e$) represents a simple path.
The player who cannot choose an edge according to the rules loses.
Show: If $G$ contains a perfect matching, then there is winning-strategy for the first player.

Given

Let $G=(V,E)$
Let $M$ be a perfect matching in $G$

Observation

If $M\subset P$ and both end edges are in $M$
→ no futher edge can be chosen.

Proof

An futher edge can only be choosen if it leads to a vertex not in $P$.
If the vertex would be in $P$, $P$ would not be a simple path.
$M$ covers all vertecies in $G$, because $M$ is perfekt,
therefore there is no edge that leads to a vertex not in $P$.

Winning strategy

The first player always chooses an edge in M.
Therefore the second player must allways choose an edge not in $M$.
The second player will loose after the first player chooses the last edge in $M$
because $M\subset P$ and both end edges are in $M$.

Assumption

1. The first player allways choose an edge in $M$.
2. Both end edges are in $M$ when the second player chooses.
3. P is an $M$ alternating path.

Proof

by induction over $n=|P|$

Start $n=0$

The first player chooses an edge in $M$. (1. Assumption)
→ 2. Assumption: both end edges are in $M$
→ 3. Assumption: the path contains only one edge in $M$

Step n’ = n + 1

• If $n\nmid 2$ (the second player chooses)
  The second player must choose an edge $(x,v)\notin M$ (2. Assumption)
  therefore $v\in M$ ($M$ is perfekt) and $v\notin P$ ($P$ is simple).

→ 3. Assumption: The second player extended the end edges whitch are in $M$ with an edge that is not in $M$.

• If $n\mid 2$ (the first player chooses)
  $\exists (v,u)\in M$
  $u\notin P$ because $P$ would need to contain two cosequtive edges that are not in $M$. (3. Assumption)

→ 1. Assumption the first player can choose $(v,u)$
→ 2. and 3. Assumption: The player first will extend the end edge that is not $M$.

At every step in the induction all three assumptions are true.
I have also marked this with the arrows →

Source

https://doi.org/10.1016/0095-8956(74)90029-X