Past exam of the computer science course of the University of Oxford / 2019 / Algorithms / 3

A parameterized decision problem is fixed-parameter tractable if there is an algorithm deciding inputs of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, where $f$ is a computable function and $c$ is a constant independent of $k$. Arbitrarily expensive dependence on the parameter is permitted; putting $k$ in the exponent of $N$ does not by itself establish fixed-parameter tractability.

For a minimization problem with nonnegative costs, a factor-two approximation algorithm runs in polynomial time, always returns a feasible solution, and satisfies $\mathrm{cost}(\mathrm{ALG})\le 2\mathrm{OPT}$ on every feasible input. A feasible solution also satisfies $\mathrm{OPT}\le \mathrm{cost}(\mathrm{ALG})$. If the optimum is zero, the guarantee requires an answer of zero cost.

The vertex cover decision problem takes a finite simple graph $G$ and a nonnegative integer $k$, and asks whether there is a vertex cover of cardinality at most $k$. The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.

For the decision problem, if there are no edges, accept; if there is an edge but $k=0$, reject. Otherwise choose an edge $uv$ and branch: either include $u$ and recurse on $G-u$ with budget $k-1$, or include $v$ and recurse on $G-v$ with budget $k-1$. Accept if either branch accepts. Every vertex cover contains at least one endpoint of $uv$, so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.

The search tree has depth at most $k$ and at most $2^k$ leaves. Processing each node in $O(|V|+|E|)$ time gives $O(2^k(|V|+|E|))$ running time, establishing fixed-parameter tractability.

For optimization, greedily build a maximal matching $M$: repeatedly select an edge and discard every edge touching either endpoint. Return the set $C$ of all endpoints of $M$. Any edge with neither endpoint in $C$ could be added to $M$, contradicting maximality; thus $C$ is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. ThereforeThe greedy construction takes polynomial time, and can be implemented in $O(|V|+|E|)$ with adjacency lists. It needs only a maximal matching, not a maximum matching.

If the basis has $r\le k$ members, it has $2^r$ subsets, each specifying a possible union. Different subsets can produce the same union, so the number of distinct generated sets is at most $2^r$. Consequently,Here $\mathcal{F}$ is a set family of distinct sets. If a representation lists duplicate input sets, discard those duplicates before applying this bound. The empty union is included.

Write $U^{\prime }=U\setminus \{y\}$ and ${\mathcal{F}}^{\prime }=\{B\setminus \{y\}:B\in \mathcal{F}\}$. If $\mathcal{A}$ is a basis for the original instance, replace each member $A$ by $A\setminus \{y\}$. Deletion commutes with unions, so the resulting family generates every member of ${\mathcal{F}}^{\prime }$ and has at most $|\mathcal{A}|$ members.

Conversely, take a basis ${\mathcal{A}}^{\prime }$ for the reduced instance. Lift each of its members byIf $B\setminus \{y\}$ is represented as a union of reduced basis sets, the same union of their lifts agrees with $B$ on $U^{\prime }$. It contains $y$ exactly when one of the selected reduced basis sets contains $x$, namely exactly when $x\in B$. By the assumed incidence equivalence in a set family, this occurs exactly when $y\in B$. Thus the lifted union is precisely $B$, and the lifted basis has no more members.

Therefore deleting $y$ preserves the yes/no answer with the same parameter $k$. The reverse construction does not require a reduced basis set to be an input set.

First discard duplicate input sets, and let $m=|\mathcal{F}|$. If $m>2^k$, reject by part (i); this rejection can be encoded as the fixed no-instance $U=\{u\}$, $\mathcal{F}=\{\{u\}\}$, $k=0$ of the set basis problem. Otherwise, represent each ground element $x$ by its incidence columnKeep one element from each class of equal columns. By repeatedly applying part (ii), this preserves the answer. The reduced number of elements $q$ satisfiesRelabel these representatives and store their reduced incidence matrix. Its $mq$ membership bits, the dimensions and $k$ have encoded length bounded solely by a computable function of $k$; the leading incidence bound is $2^{k+2^k}$. Thus this is a kernelization, even though it is not a polynomial kernel. Forming columns and grouping identical ones takes polynomial time in the original explicit input length. To test $m>2^k$, compare bit lengths or truncate exponentiation at $m+1$; never construct an enormous $2^k$ merely to perform this preprocessing comparison.

For completeness, the bounded instance can be solved explicitly. Enumerate all ordered lists of $k$ subsets of the $q$-element ground set, allowing empty members to pad shorter bases. There are at most $2^{kq}$ such lists. For a candidate basis and each reduced input set $B$, form the union of every candidate basis set contained in $B$. If this union equals $B$, a representation exists; if it does not, no union of that candidate's members can represent $B$, because any member not contained in $B$ would add a forbidden element. Testing every $B$ therefore verifies a candidate in time polynomial in $m,q,k$.

The preprocessing is polynomial in the original input length, and the remaining search depends only on $k$. Hence the set basis problem is fixed-parameter tractable with respect to $k$. Empty input families and $k=0$ are covered by the same empty-union convention.

Assume the standard nonempty instance convention $1\le k\le n$, and set $d(v,v)=0$. Start with no centers. Pick any city still farther than $2r^{\ast }$ from every selected center, add it as a center, and mark every city within distance $2r^{\ast }$ of it as covered. Stop when all cities are covered.

Distinct chosen centers have pairwise distance greater than $2r^{\ast }$. Fix an optimal set of $k$ centers and assign each city to one optimal center within distance $r^{\ast }$. Two cities assigned to the same center have distance at most $2r^{\ast }$ by the triangle inequality. Thus no two chosen centers can be assigned to that same optimal center. The pigeonhole principle shows that the greedy procedure selects at most $k$ centers and has radius at most $2r^{\ast }$. If fewer than $k$ are selected, add arbitrary distinct cities; this cannot worsen the radius.

With the supplied radius, a straightforward implementation updates coverage in $O(n)$ time per selected center, hence takes $O(nk)$ distance tests. The argument also handles $r^{\ast }=0$. It is the packing bound underlying the metric k-center problem.

The optimum radius is a distance from some city to a selected city, so it belongs toSort the distinct values of $D$, try them in increasing order, and run part (i)'s greedy procedure with each trial value $r$. Declare a trial successful when all cities are covered using at most $k$ centers; stop a failed trial as soon as a $(k+1)$st center would be selected. The trial $r=r^{\ast }$ must succeed by part (i), so the first successful value $\hat{r}$ satisfies $\hat{r}\le r^{\ast }$. Its output hasThere are $O(n^2)$ candidate distances and $O(n^2)$ work per trial, giving a polynomial-time algorithm with running time $O(n^4)$, plus sorting. Success at $r$ need not mean that radius $r$ itself is feasible; only the radius-$2r$ guarantee is used.

A faster alternative is the farthest-first traversal. Choose any first center, then repeatedly choose a city farthest from its nearest current center until $k$ have been chosen. Let $R$ be the resulting radius. If $R>0$, adjoin a city attaining that distance. At every earlier selection, the maximum distance to the then-current center set was at least $R$, so all pairs among these $k+1$ cities are at distance at least $R$. Two belong to the same optimal radius-$r^{\ast }$ closed ball, giving $R\le 2r^{\ast }$ by the triangle inequality. If $R=0$, the guarantee is immediate. Maintaining nearest-center distances gives $O(nk)$ distance evaluations without knowing $r^{\ast }$.