Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 2

For a finite undirected graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ meeting every edge: for every $\{u,v\}\in E$, at least one of $u,v$ belongs to $C$. The optimization problem asks for a vertex cover of minimum cardinality. Its usual decision version also supplies an integer $k$ and asks whether one exists with $|C|\le k$.

Construct a set cover problem instance whose universe is the set of edges $E$. For each vertex $v\in V$, supply the set $S_v$ of all edges incident to $v$. A collection $\{S_v:v\in C\}$ covers the universe if and only if every edge has an endpoint in $C$, which is precisely the vertex cover condition.

The correspondence preserves cardinality: a vertex cover of size $k$ is a feasible solution of the set cover problem using $k$ of these sets, and conversely. If two labelled vertices produce identical sets, one can keep their labels or discard duplicate choices without changing the optimum. The construction has size $O(|V|+|E|)$ when incidences are listed, so it is a polynomial-time reduction.

Root the tree arbitrarily. For each vertex $v$, let $D_1(v)$ be the minimum vertex cover size in its descendant subtree, conditional on selecting $v$, and $D_0(v)$ the corresponding minimum conditional on omitting $v$. Process the vertices in postorder traversal. For every child $u$ of $v$,At a leaf of a rooted tree, the empty sums give $D_1=1,D_0=0$. Return $\min \{D_0(r),D_1(r)\}$ at the root $r$.

For algorithm correctness, if $v$ is selected, each child subtree may independently use its cheaper state, since the connecting edge is already covered by $v$. If $v$ is omitted, each child must be selected to cover its connecting edge. Distinct child subtrees have no edges between them because the input is a tree. These observations prove the recurrences by structural induction. Each edge contributes constant work once, giving $O(|V|)$ time complexity and $O(|V|)$ space with adjacency lists. The single-vertex tree correctly has optimum zero. This is minimum vertex cover of a tree by dynamic programming.

In depth-first search of an undirected graph, every edge joins a vertex to one of its ancestors or descendants in the discovery tree. To see this directly, suppose $u$ is discovered before its neighbour $v$. If $v$ is still undiscovered, the search from $u$ cannot finish before discovering $v$: it eventually scans $uv$. Thus $v$ is discovered while the call for $u$ remains active and belongs to its descendant subtree.^[ref]

For any edge $uv$, its ancestor endpoint therefore has a proper descendant and hence at least one child. It is an internal vertex of a rooted tree. Every edge has an internal endpoint, so the internal vertices form a vertex cover. The relevant leaves of a rooted tree here have no children in the rooted discovery tree; a root of vertex degree one can still be internal.

We construct an injection from the unmatched vertices in a matching to the leaves of a rooted tree. Start a downward graph path at each unmatched vertex $u$. If the current vertex is a leaf of a rooted tree, stop. Otherwise choose any child $v$. The current vertex is either the unmatched starting point or a vertex already matched to its own parent.

In either case, $v$ cannot be unmatched: the proper matching in a rooted tree condition would require its parent to be matched to one of $v$'s siblings in a rooted tree, whereas that parent is either unmatched or already matched upward. Nor can $v$ be matched to its parent. Its matching partner must therefore be one of its own children, say $w$. Extend the graph path by the two edges to $v$ and then to $w$, and continue from $w$.

Every extension descends two levels, so finiteness guarantees termination at a leaf of a rooted tree. Every visited vertex except the starting point is matched. The constructed graph paths for different unmatched starting points are disjoint: if two downward graph paths in a tree meet, one starting point must lie on the other path, which would put a second unmatched vertex after the first. That is impossible. Hence their terminal leaves of a rooted tree are distinct, provingOnly the properness condition for unmatched non-root vertices was used. If the root is unmatched and the convention exempts it because it has no parent, the same construction starts there and still works. Thus the root convention does not affect the claimed inequality. This proves the unmatched-vertex bound for a proper tree matching without requiring $M$ to have maximum size.

For a connected graph with at least one edge, run depth-first search and output the set $I$ of internal vertices of a rooted tree in its discovery tree $T$. Part (d) proves that $I$ is a vertex cover. It is also connected: every ancestor of an internal vertex is internal, so the graph path in $T$ from that vertex to the root stays inside $I$. The root is internal when $|V|\ge 2$.

For the approximation guarantee, choose a maximum-size proper matching in a rooted tree $M$ of $T$, whose existence is supplied. It is used only in the analysis; the algorithm need not construct it. Since every matched edge uses two distinct vertices,By part (e), $|L(T)|\ge |U(M)|$. ThereforeThe final inequality holds because every vertex cover of $G$, connected or otherwise, must use at least one distinct endpoint for each of the disjoint edges in $M\subseteq E(G)$. Thus this is a 2-approximation algorithm in $O(|V|+|E|)$ time complexity.

For completeness, a disconnected input needs a feasibility check: if two different connected components of a graph contain edges, no connected vertex cover can meet both. If exactly one component contains edges, run the construction on that component and ignore isolated vertices. If there are no edges, the empty vertex cover is optimal when an empty solution is permitted; if a nonempty connected solution is required, any single vertex is optimal for a nonempty input. These conventions cover the boundary cases omitted from the main approximation argument.