15.4. Kernelization via Linear Programming

As an example to illustrate how linear programming can be used as a kernelization technique, let us focus on the vertex cover problem again. The following is the vertex cover problem expressed as an integer linear program:

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

\(x_v = 1\) if and only if \(v\) is in the vertex cover. The constraint \(x_u + x_v \ge 1\) for every edge \((u, v) \in E\) ensures that every edge has at least one endpoint in the vertex cover. Finally, we aim to minimize the size \(\sum_{v \in V} x_v\) of the vertex cover. To obtain a small problem kernel, we solve the LP relaxation of (15.1):

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

Given a solution \(\hat x\) of (15.2), we use it to split the vertex set \(V\) of \(G\) into three sets \(V_0\), \(V_{1/2}\), and \(V_1\):

\[\begin{aligned} V_0 &= \bigl\{ v \in V \mid \hat x_v < \textstyle\frac{1}{2} \bigr\}\\ V_{1/2} &= \bigl\{ v \in V \mid \hat x_v = \textstyle\frac{1}{2} \bigr\}\\ V_1 &= \bigl\{ v \in V \mid \hat x_v > \textstyle\frac{1}{2} \bigr\} \end{aligned}\]

The problem kernel we return is \((G_{1/2}, k - |V_1|)\), where \(G_{1/2} = G[V_{1/2}]\) is the subgraph of \(G\) induced by the vertices in \(V_{1/2}\). The next lemma shows that this reduction rule is sound.

Lemma 15.17: \(G\) has a vertex cover of size at most \(k\) if and only if \(G_{1/2}\) has a vertex cover of size at most \(k - |V_1|\).

Proof: First assume that \(G_{1/2}\) has a vertex cover \(C\) of size at most \(k - |V_1|\). Then the set \(C \cup V_1\) has size \(|C| + |V_1| \le k\). We prove that \(C \cup V_1\) is a vertex cover of \(G\). Consider an arbitrary edge \(e = (u, v) \in E\). If \(e\) has both endpoints in \(V_{1/2}\), then \(e \in G_{1/2}\), so \(e\) is covered by \(C \subseteq C \cup V_1\). If \(e\) has at least one endpoint in \(V_1\), then \(e\) is covered by \(V_1\). If \(e\) has no endpoint in \(V_1\) and does not have both its endpoints in \(V_{1/2}\), then w.l.o.g. \(u \in V_0\) and \(v \in V_0 \cup V_{1/2}\). Thus, \(\hat x_u + \hat x_v < \frac{1}{2} + \frac{1}{2} = 1\), a violation of \(e\)'s edge constraint in (15.2).

Now assume that \(G\) has a vertex cover \(C\) of size at most \(k\). The key is to show that there exists such a vertex cover that includes \(V_1\). Indeed, this implies that \(G_{1/2}\) has a vertex cover of size at most \(k - |V_1|\) because \(C \cap V_{1/2}\) is a vertex cover of \(G_{1/2} = G[V_{1/2}]\) and \(|C \cap V_{1/2}| \le |C| - |V_1| \le k - |V_1|\) if \(V_1 \subseteq C\).

So consider some vertex cover \(C\) of \(G\) of size \(|C| \le k\) and assume that \(V_1 \not\subseteq C\). Let \(C_0 = V_0 \cap C\), \(\bar C_1 = V_1 \setminus C\), and \(C' = C \setminus C_0 \cup \bar C_1\). Clearly, \(V_1 \subseteq C'\). Thus, it suffices to prove that \(C'\) is also a vertex cover of \(G\) and that \(|C'| \le |C| \le k\).

To prove that \(C'\) is a vertex cover, consider an arbitrary edge \((u, v) \in E\). If \(u, v \notin C_0\), then \(\{u, v\} \cap C' \supseteq \{u, v\} \cap C \ne \emptyset\), so \(C'\) covers the edge \((u, v)\). If w.l.o.g., \(u \in C_0\), then \(u \in V_0\), that is, \(\hat x_u < \frac{1}{2}\). Since \(\hat x_u + \hat x_v \ge 1\), this implies that \(\hat x_v > \frac{1}{2}\) and, thus, \(v \in V_1\). Since \(V_1 \subseteq C'\), \(C'\) covers the edge \((u, v)\) also in this case.

To prove that \(|C'| \le |C|\), it suffices to prove that \(|C_0| \ge \bigl|\bar C_1\bigr|\) because \(|C'| = |C| - |C_0| + \bigl|\bar C_1\bigr|\). Assume for the sake of contradiction that \(|C_0| < \bigl|\bar C_1\bigr|\), let \(\delta = \min \bigl\{ \hat x_v - \frac{1}{2} \mid v \in \bar C_1 \bigr\} > 0\),¹ and let

\[\tilde x_v = \begin{cases} \hat x_v - \delta & v \in \bar C_1\\ \hat x_v + \delta & v \in C_0\\ \hat x_v & \text{otherwise}. \end{cases}\]

Next we prove that \(\tilde x\) is a feasible solution of (15.2). Since \(\sum_{v \in V} \tilde x_v - \sum_{v \in V} \hat x_v = \delta\bigl|C_0\bigr| - \delta|\bar C_1| < 0\) (because \(|C_0| < \bigl|\bar C_1\bigr|\)), this gives the desired contradiction to the fact that \(\hat x\) is an optimal solution of (15.2).

For every vertex \(v \in V \setminus \bigl(C_0 \cup \bar C_1\bigr)\), we have \(\tilde x_v = \hat x_v\). Since \(\hat x_v \ge 0\), this implies that \(\tilde x_v \ge 0\). If \(v \in \bar C_1\), then \(\frac{1}{2} = \hat x_v - \bigl(\hat x_v - \frac{1}{2}\bigr) \le \hat x_v - \delta\). Since \(\tilde x_v = \hat x_v - \delta\), this shows that \(\tilde x_v \ge 0\) also for \(v \in \bar C_1\). Finally, if \(v \in C_0\), then \(0 \le \hat x_v < \hat x_v + \delta\). Since \(\tilde x_v = \hat x_v + \delta\), this shows that \(\tilde x_v \ge 0\) for all \(v \in C_0\). Thus, every vertex \(v \in V\) satisfies \(\tilde x_v \ge 0\).

Now consider the edge constraint associated with an arbitrary edge \((u, v)\). If \(u, v \notin \bar C_1\), then \(\tilde x_u + \tilde x_v \ge \hat x_u + \hat x_v \ge 1\). If w.l.o.g. \(u \in \bar C_1\), then we distinguish two cases. If \(v \in V_{1/2} \cup V_1\), then \(\tilde x_v \ge \frac{1}{2}\). Since \(\tilde x_u \ge \frac{1}{2}\), we have \(\tilde x_u + \tilde x_v \ge 1\) in this case. If \(v \in V_0\), then \(v \in C_0 = C \cap V_0\) because \(u \notin C\) and \(C\) is a vertex cover of \(G\). Thus, \(\tilde x_u + \tilde x_v = (\hat x_u - \delta) + (\hat x_v + \delta) = \hat x_u + \hat x_v \ge 1\). This shows that \(\tilde x\) is a feasible solution of \cref{eq:vertex-cover-lp-kernelization} and we obtain the desired contradiction. ▨

The next lemma shows that either \((G, k)\) is a no-instance and, by Lemma 15.17, so is \((G_{1/2}, k - |V_1|)\) or \(|V_{1/2}| \le 2k\).

Lemma 15.18: If \(G\) has a vertex cover of size at most \(k\), then \(|V_{1/2}| \le 2k\).

Proof: Since \(G\) has a vertex cover of size at most \(k\), (15.1) has a solution with objective function value at most \(k\). Thus, (15.2) also has a solution with objective function value at most \(k\). Since \(\hat x\) is an optimal solution of (15.2), this implies that

\[\begin{aligned} k &\ge \sum_{v \in V} \hat x_v \ge \sum_{v \in V_{1/2}} \hat x_v = \sum_{v \in V_{1/2}} \frac{1}{2} = \frac{|V_{1/2}|}{2}.\\ 2k &\ge |V_{1/2}|.\ \text{▨} \end{aligned}\]