# Notes - ADS HT24, Kernelisation

### Flashcards

Suppose we have a decision problem $\mathcal D$ with parameter $k$. What is the process of kernelisation, and why is it useful?

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.

Suppose we have a decision problem $\mathcal D$ with parameter $k$, and we have a corresponding kernalisation, i.e. 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$)

In particular:

- $(I’, k’)$ is called a kernel
- $f(k)$ is called the size of the kernel

What does it mean for $\mathcal D$ to admit a polynomial kernel, and a linear kernel?

- 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

Suppose we have a decision problem $\mathcal D$ with parameter $k$, and we have a corresponding kernalisation, i.e. 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$)

What relationship is there between fixed-parameter tractability and kernelisation?

Suppose we have a decision problem $\mathcal D$ with parameter $k$, and we have a corresponding kernalisation, i.e. 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$)

How can we obtain a FPT algorithm from a kernelisation algorithm?

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

Suppose we have a decision problem $\mathcal D$ with parameter $k$, and want to find some kernalisation, i.e. a polynomial time algorithm that maps an instance $(I, k)$ to smaller instances $(I’, k’)$ with $k’ \le k$ and $ \vert I’ \vert \le f(k)$.

In this context, what is a reduction rule?

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

The $\mathbf{LineCover}$ decision problem is

- Input: Set $P$ of $n$ points in the plane, integer $k$
- Output: Are there $\le k$ lines in the plane that cover all the points?

Quickly describe an FPT algorithm for this problem based on a reduction rule.

- Input: Set $P$ of $n$ points in the plane, integer $k$
- Output: Are there $\le k$ lines in the plane that cover all the points?

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})$.

The $\mathbf{VertexCover}$ decision problem is:

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

Quickly describe an $O(k^{2k} \vert E \vert )$ FPT algorithm for this problem based on reduction rules.

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

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})$).

The $\mathbf{VertexCover}$ decision problem is:

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

Can you describe an exponential kernel for vertex cover that uses the $O(2^k \vert E \vert )$ bounded search tree algorithm as a subroutine?

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

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$.

The $\mathbf{VertexCover}$ decision problem is:

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

Assuming without proof that in the linear programming relaxation of vertex cover you can partition the $x _ v$ in a optimal solution into three sets where $x _ v \in \{0, 1/2, 1\}$, can you describe a linear kernel for vertex cover?

- Input: Graph $G = (V, E)$, integer $k$
- Output: Is there a vertex cover of size $\le k$, where a vertex cover is a set $S \subseteq V$ such that every edge $e \in E$ is incident to some vertex in $S$.

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|\]If we have a collection of sets $\mathcal F \subset \mathcal P(U)$ such that $\mathcal F \le 2^k$ and for all pairs $(x, y) \in U \times U$, $\exists f \in \mathcal F$ such that $x \in f$ but $y \notin f$, can you give an upper bound on the number of different elements of $U$ contained in the sets in $\mathcal F$?

Can you define the $k\mathbf{-Center}$ problem?

- 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

The $k\mathbf{-Center}$ problem is:

- 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 \{d(u, v _ 1), \cdots, d(u, v _ k)\}$ is minimised

Quickly describe a $2$-approximation algorithm for this problem, first by assuming that we know the optimal radius $r^\star$, and then without assuming we know the optimal radius?

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.