Notes - ADS HT24, Approximation algorithms

For every instance $x$ of $\mathcal P$, the value $\mathcal A(x)$ of the solution produced by $\mathcal A$ and the optimal solution $\text{Opt}(x)$ satisfy:

• For minimisation problems: $\mathcal A(x) \le \rho \cdot \text{OPT}(x)$
• For maximisation problems: $\mathcal A(x) \ge \rho \cdot \text{OPT}(x)$

Note that the algorithm implicitly computes a maximal matching (a matching is a collection of edges that have no common vertices, and a matching $M$ is maximal if there is no matching $M’$ such that $M \subseteq M’$):

C = [] # the cover
M = [] # the matching

while there is an edge e = (u, v) not covered by C:
	add u to C
	add v to C
	add e to M

return C

Then $ \vert C \vert = 2 \vert M \vert $ ($M$ contains edges, and there are two vertices corresponding to each edge). This matching is maximal because of the structure of the while loop. We also must have that

since given any matching $M$, any vertex cover must cover all the edges in the matching, and each vertex in the vertex cover covers just one edge in the matching, but assumption that the edges in the matching are disjoint.

So in particular if $C^\star$ is the optimal such cover:

Then, chaining these together:

The vertex cover must cover every edge in the matching, and since by assumption the edges in $M$ are disjoint from one another, one vertex in $C$ can only cover one edge.

The strong duality is given by Kőnig’s theorem, which states that in bipartite graphs

Key idea: We can show the greedy strategy decreases the remaining uncovered elements by a multiplicative factor that depends on $k = \vert C^\star \vert $.

Some notation:

• Let $C^\star$ be an optimal solution to the problem
• $k = \vert C^\star \vert $

We want to show that $ \vert C \vert \le (1 + \ln n)k$.

Suppose at iteration $t$ of the while loop we have $n _ t$ elements that are yet to be covered. Then $C^\star$ gives a (potentially bad) covering of these elements of size $k$. Thus by the pigeonhole principle, there must exist some set in $C^\star$ that covers at least $n _ t / k$ of these elements (otherwise this cover wouldn’t be big enough, also note that we haven’t used this set yet since by assumption we are dealing with elements not in our cover).

This implies that

Which implies in general

(since at the start of the algorithm there are $n$ elements yet to be covered, and are using the fact that for all $x \in R$, $1 + x \le e^x$ which can be proved by considering the Taylor expansion of $e^x$). We want $n _ t$ to be zero, or alternatively that $n _ t < 1$. This happens when $t > k \ln n$, since

So after $k \ln n$ steps, $n _ t = 0$. Thus $ \vert C \vert < k \ln n$, or alternatively $ \vert C \vert \le 1 + k \ln n$. This implies that $ \vert C \vert \le (1 + \ln n)k$ as required.

Let $\mathcal A$ be a polynomial time $\alpha$-approximation algorithm for the $\mathbf{MinTSP}$ problem. We aim to show that if such an algorithm exists, we can actually use it to decide whether an arbitrary graph has a Hamiltonian cycle, which is NP-complete.

Let $G = (V, E)$ be the graph for which we want to determine if it has a Hamiltonian cycle.

Define a cost function $c : V \times V \to \mathbb R _ {\ge 0}$ as follows:

This means $(V, c)$ defines an instance of $\mathbf{MinTSP}$. We want to show

Suppose $G$ has a Hamiltonian cycle. Then the TSP on $(V, c)$ has a solution with total cost $1$, which means $\mathcal A$ returns a solution with cost $\le \alpha$.

Suppose $G$ does not have a Hamiltonian cycle. Then any Hamiltonian cycle in $(V, c)$ uses an edge not in $G$, so $\mathcal A$ will return a solution with cost $\ge 2\alpha$.

Hence, by checking if the cost is $\le \alpha$, we can determine if an arbitrary graph has a Hamiltonian cycle.

• Find an MST $T$
• Find a tour $\mathcal T$ (a walk that starts and ends at the same vertex, possibly repeating edges) by traversing edges of $T$ in DFS order
• Remove duplicated vertices in the tour (called “shortcutting”, this is where we use the triangle inequality and also the fact that the graph is complete)
• Output this list of vertices

Let $c(\cdot)$ denote the cost of some graph by summing along the costs along the edges. We want to show $c(\mathcal T’) \le 2\text{OPT}$.

• Note that $c(\mathcal T’) \le c(\mathcal T)$ because of the triangle inequality. If $\mathcal T$ visits vertices $v _ 1, \cdots, v _ {i-1}, v _ i, v _ {i+1}, v _ n$ where $v _ i$ is repeated, then $c(\mathcal T) - c(\mathcal T \setminus \{v _ i\}) = c(v _ {i-1}, v _ i) + c(v _ i, v _ {i+1}) - c(v _ {i-1}, c _ {i+1}) \ge 0$.
• Also $c(\mathcal T) = 2c(T)$, since we double the number of edges in the MST.
• Finally $c(T) \le \text{OPT}$, since an optimal TSP induces a spanning tree, but we could just remove edges until we get a spanning tree, which must be at least as large as $c(T)$.

Hence overall:

A walk that starts and ends at the same vertex, and visits every vertex at least once.

A sequence of vertices edges in a graph.

Then if the graph contains a Hamiltonian cycle, the minimum travelling salesperson tour has weight $1$. If it doesn’t, then the minimum tour has cost at least $\alpha$, which means we could distinguish these cases with our approximation algorithm.

• $I$ is a positive instance: we can come up with an instance of the minimisation problem with cost $\le n+1$.
• $I$ is a negative instance: The minimisation problem has cost $> n + 1$

This is because $(n+1) \cdot (1 + \frac {1}{n+1}) = n + 1 + 1 = n + 2$, so the approximation algorithm would have to tell if it was a positive instance.