Notes - ADS HT24, Kernelisation

A polynomial time algorithm that maps an instance $(I, k)$ to an instance $(I’, k’)$ such that:

• $(I, k)$ is a YES-instance of $\mathcal D$ $\iff$ $(I’, k’)$ is a YES-instance of $\mathcal D$
• $k’ \le k$
• $ \vert I’ \vert \le f(k)$ for some computable function $f(k)$ (note the dependence only on $k$)

This is a useful concept because it formalises the idea of finding the “core” of a problem.

• If $f(k) = k^{O(1)}$, then the problem admits a polynomial kernel
• If $f(k) = O(k)$, then the problem admits a linear kernel

\[\mathcal D \text{ has kernelisation algorithm} \iff \mathcal D \text{ is FPT}\]

• Create the kernel $(I, k)$
• Brute force the size of the reduced instance

A rule that reduces the size of the input and preserves the answer to the problem.

We need to find a reduction rule. One is based on the fact that:

If any line covers $> k$ points, then this line must be in any line cover of size $k$.

(Why is this true? Suppose there exists some line $\ell$ covering $>k$ points. All of these points are then colinear. In any solution, there must be at least one line that covers at least two of these points simultaneously, since otherwise we would need $>k$ points to hit each one. But then this line bust be the same as $\ell$, since $\ell$ is uniquely determined by two points).

This gives the reduction rule:

If a line covers a set $S$ of points with $ \vert S \vert > k$, then $(P; k) \mapsto (P\setminus S; k-1)$ is an equivalent instance of the problem.

Thus we can apply this reduction rule iteratively until it no longer applies. We get a chain:

\[(P; k) \mapsto \cdots \mapsto (P'; k')\]

and $(P, k)$ is a YES-instance iff $(P’, k’)$ is a YES-instance.

Finally:

• If $ \vert P’ \vert > k^2$, then output NO (since no line covers more than $k$ points in $P’$)
• If $ \vert P’ \vert \le k^2$, brute force over choice over $k’$ lines (at most $(k^2)^{2k’} \le k^{4k}$ choices, since there are $\le k^2$ possible points, and we need to pick $2$ possible points each time for each line).

Then the total running time is $O(n^2 + k^{4k})$.

Given $(G, k)$, we have two reduction rules:

• If $v$ is isolated, reduce to $(G \setminus \{v\}, k)$.
• If $v$ has $> k$ neighbours, recurse on $(G \setminus \{v\}, k-1)$

Applying reduction rules iteratively, we get the chain

\[(G, k) \mapsto \cdots \mapsto (G', k')\]

Now every vertex in $G’$ has degree at least one and at most $k$. Then:

• If $G’$ has $>k^2$ edges, output NO (since no vertex cover of size $k’ \le k$ can cover all the edges)
• If $G’$ has $\le k^2$ edges, $(G’, k’)$ is a kernel. This is a kernel, since $k’ \le k$, $ \vert E’ \vert \le k^2$ and $ \vert V’ \vert \le 2 \vert E’ \vert \le 2k^2$ (because every vertex has degree at least $1$), we have a $O(k^{2k} \vert E \vert )$ algorithm (since $k^2 \choose k$ is $O(k^{2k})$).

Given an instance $G = (V, E)$, integer $k$, our goal is to output in polynomial time in $k$ a kernel $(G’, k’)$ with $k’ \le k$ and $ \vert G’ \vert \le 2^k$.

If $ \vert G \vert < 2^k$, then $(G, k)$ is a kernel of size $2^k$ (i.e. the identity mapping $(G, k) \mapsto (G, k)$, since $ \vert G \vert \le 2^k$, and $k \le k$).

If $ \vert G \vert \ge 2^k$, running the $O(2^k \vert E \vert )$ bounded search tree algorithm is $O( \vert G \vert ^2)$, so it counts as polynomial time in $k$ (this is kind of stupid, but we’re highlighting black-box techniques like these lead to big kernels – it’s much more useful to have a linear or polynomial kernel).

Once we’ve run the bounded search tree algorithm we can output a trivial YES / NO instance, e.g. $G’ = \bigcirc$, $k’ = 0$ for YES, or $G’ = \bigcirc-\bigcirc$, $k’ = 0$ for $k$.

Let $G$ be an instance of $\mathbf{MinVertexCover}$ and let $C^\star$ be a minimum vertex cover. We have the relaxed linear program

\[\begin{aligned} \min \quad& \sum_{v \in V} x_v \\\\ \text{s.t.} \quad & x_u + x_v \ge 1 \quad \forall (u, v) \in E \\\\ \quad & 0 \le x_v \le 1 \quad \forall v \in V \end{aligned}\]

We know that if $\{x _ v^\star\}$ is an optimal solution to the relaxed LP, then $ \vert C^\star \vert \ge \sum _ {v \in V} x _ v^\star$ and that taking $C = \{v \mid x _ v^\star \ge 1/2\}$ gives a 2-approximation, i.e. $ \vert C \vert \le 2 \vert C^\star \vert $.

---

We want to show that there exists a min vertex cover $C^\star$ such that $C^\star \le C$, i.e. we can find an optimal vertex cover as a subset of our approximation. This gives a linear kernel, if $\sum _ {v \in V} x^\star _ v > k$ we can output NO, and otherwise let $G ‘$ be the induced subgraph on $C$, which must have at most $ \vert C \vert \le 2 \sum _ {v \in V}x^\star _ v \le 2k$ vertices, so we can brute force the choice vertices in $G’$ in time $2^{2k} \vert E \vert $.

By the assumption in the question, for all $v \in V$ it holds that

\[x_v^\star \in \\{0, 1/2, 1\\}\]

Let

\[\begin{aligned} V_0 &= \\{v \mid x^\star_v = 0\\} \\\\ V_{1/2} &= \\{v \mid x^\star_v = 1/2\\} \\\\ V_1 &= \\{v \mid x^\star_v = 1\\} \end{aligned}\]

Suppose wlog that $C^\star \cap V _ 0 \ne 0$. Then let

\[C' = C^\star \cup (V_1 \setminus C^\star) \setminus(V_0 \cap C^\star)\]

We need to show two things: $C’$ is a vertex cover, and $ \vert C’ \vert \le \vert C^\star \vert $ (in which case actually $ \vert C’ \vert = \vert C^\star \vert $, and it is also optimal).

The only way $C’$ could fail to be a vertex cover is if there is an edge between $V _ 0$ and $V _ 0 \cup V _ {1/2}$, but this can’t happen since $x^\star$ is a feasibel solution to the relaxed LP.

To see $ \vert C’ \vert \le \vert C^\star \vert $, note that $ \vert C’ \vert = \vert C^\star \vert + \vert V _ 1 \setminus C^\star \vert - \vert C^\star \cap V _ 0 \vert $ (this can be seen by the fact that $C^\star$ and $(V _ 1 \setminus C^\star) \setminus(V _ 0 \cap C^\star)$ are disjoint).

Then let

\[x_v = \begin{cases} \frac 1 2 &\text{if }v \in (V_1 \setminus C^\star) \cup (V_0 \cap C^\star) \\\\ x^\star_v &\text{otherwise } \end{cases}\]

$x _ v$ is a feasible solution for the LP. By the assumption that $x^\star$ is an optiomal solution, we have

\[\sum_{v \in V} x^\star_v - \sum_{v \in V} x_v \le 0\]

But, expanding out:

\[\begin{aligned} & \sum_{v \in V} x^\star_v - \sum_{v \in V} x_v \\\\ =& \sum_{v \in V} (x^\star_v - x_v) \\\\ =&\sum_{v \in (V_1 \setminus C^\star) \cup (V_0 \cap C^\star)} (x^\star_v - 1/2) \\\\ =&\sum_{v \in (V_1 \setminus C^\star)} (x^\star_v - 1/2) + \sum_{v \in (V_0\cap C^\star)} (x_v^\star - 1/2) \\\\ =&\sum_{v \in (V_1 \setminus C^\star)} (1/2) + \sum_{v \in (V_0\cap C^\star)} (- 1/2) \\\\ =& \frac{1}{2} (|V_1 \setminus C^\star| - |C^\star - V_0|) \end{aligned}\]

But then since $ \vert C’ \vert = \vert C^\star \vert + \vert V _ 1 \setminus C^\star \vert - \vert C^\star \cap V _ 0 \vert $, this implies overall that

\[|C'| \le |C^\star|\]

\[2^{2^k}\]

• Input: $V \times V$ complete graph, $d$ symmetric $\mathbb N$-valued satisfying triangle inequality, $k$ integer
• Output: $k$ centers $v _ 1, \cdots, v _ k \in V$ so that the radius $r = \max _ {u \in V} \min _ {i = 1, \cdots, k} d(u, v _ i)$ is minimised

For a vertex $v$ and radius $r$, let

\[D(v, r) = \\{u \in V \mid d(u, v) \le r\\}\]

i.e. the set of vertices at distance at most $r$ from $v$.

Let $V _ 1 = V$. At step $t = 1, \cdots, k$, pick an arbitrary vertex $v _ t \in V _ t$ and let

\[V_{t+1} = V_t \setminus D(v_t, 2r^\star)\]

Claim: $V _ {k+1} = \emptyset$. Let $v _ 1^\star, \cdots, v _ k^\star$ be centers achieveing the optimum. Then

\[V = \bigcup^k_{i = 1} D(v_i^\star, r^\star)\]

Note that for any $j = 1, \cdots, k$, $v _ j$ must belong to some set $D(v _ i^\star, r^\star)$. Then by the triangle inequality, we obtain

\[D(v_i^\star, r^\star) \subseteq D(v_j, 2r^\star)\]

So

\[\bigcup^k_{i = 1} D(v_i^\star, r^\star) \subseteq \bigcup_{i = 1}^k D(v_i, 2r^\star)\]

Therefore

\[V_{k+1} = \emptyset\]

If $V _ {k+1} = \emptyset$, then we “clearly have”

\[\max_{u \in V} \min \\{d(u, v_1), \cdots, d(u, v_k)\\} \le 2r^\star\]

To remove the dependence on knowing $r^\star$, note that the optimal radius must equal some distance $d(u, v)$. We can then guess the value of $r^\star$ by trying all distances in increasing order. For a particular value of $r$, we run the greedy algorithm above and check whether $V _ {k+1} = \emptyset$. If so, we stop and output the $k$ centers we obtained. Note that if the check fails, then we can be sure that $r < r^\star$, whereas if the check succeeds, we know that $r^\star \le 2r$. In particular, If $r _ 1, \cdots, r _ i$ are the values that we tried until we stopped, then $r _ i \le r^\star \le 2r _ i$ and hence our solution achieves a factor $2$ approximation.