15. Data Reduction and Problem Kernels

Consider an instance \((I, k)\) of a parameterized decision problem \(\Pi\).

A data reduction rule transforms \((I, k)\) into a new instance \((I', k')\) of \(\Pi\) such that \((I, k)\) is a yes-instance if and only if \((I', k')\) is a yes-instance. In this case, we call the reduction rule sound or safe.

This means that we can decide whether \((I, k)\) is a yes-instance by deciding whether \((I', k')\) is a yes-instance. If \((I', k')\) is "smaller" than \((I, k)\)—usually \(k' \le k\) and \(|I'| \le |I|\) and at least one of these two inequalities is strict)—then this is a promising technique to obtain a fast algorithm to solve \(\Pi\). Specifically, we apply the data reduction until it is no longer applicable.

We call an instance \((I,k)\) fully reduced with respect to a set of data reduction rules if none of the rules can be applied to \((I,k)\).

If each reduction rule is efficient to implement and the final fully reduced instance is small, then we obtain a fast algorithm for solving \(\Pi\) by constructing a fully reduced instance and then solving \(\Pi\) on this instance, possibly using some brute-force algorithm.

A kernelization procedure is a set of reduction rules with the following three properties:

• The instance \((I',k')\) produced by applying any of these rules to an instance \((I,k)\) satisfies \(k' \le k\).
• There exists a computable monotonically non-decreasing function \(f(k)\) such that any fully reduced instance \((I,k)\) with respect to these rules of size \(|I| > f(k)\) is guaranteed to be a yes-instance or a no-instance.
• Constructing a fully reduced instance from an arbitrary instance \((I,k)\) by applying these reduction rules takes \(O(|I|^c)\) time, for some constant \(c\).

Given an instance \((I,k)\), we call the fully reduced instance \((I',k')\) obtained from \((I,k)\) by repeated application of the reduction rules the problem kernel of \((I,k)\).

Since constructing this kernel from \((I,k)\) takes \(O(|I|^c)\) time, the kernel intuitively represents the hard core of the problem, hence the term "kernel".

If we can solve any instance \((I,k)\) in \(O(g(|I|))\) time, for some monotonically non-decreasing function \(g\), a kernelization procedure for \(\Pi\) gives us a parameterized algorithm for \(\Pi\) with running time \(O(g(f(k)) + h(k) + |I|^c)\) time, where \(h(k)\) is the time it takes to compute \(f(k)\), which we also assume is monotonically non-decreasing: Assume for concreteness that any fully reduced instance \((I,k)\) with \(|I| > f(k)\) is a no-instance. Then given any instance \((I,k)\), we construct its problem kernel \((I',k')\) in \(O(|I|^c)\) time. Since \((I,k)\) is a yes-instance if and only if \((I',k')\) is a yes-instance, it suffices to decide whether \((I',k')\) is a yes-instance. We compute \(f(k')\) in time \(h(k') \le h(k)\). If \(|I'| > f(k')\), then we answer that \((I',k')\) (and thus \((I,k)\)) is a no-instance. If \(|I'| \le f(k')\), we can decide in \(O(g(|I'|)) = O(g(f(k'))) = O(g(f(k)))\) time whether \((I',k')\) is a yes-instance. Thus, the running time of the algorithm is \(O(g(f(k)) + h(k) + |I|^c)\).

The remainder of this chapter is organized as follows:

• In Section 15.1, we prove that a problem is fixed-parameter tractable if and only if it has a problem kernel. This result is of purely theoretical interest because it sheds no light on techniques to obtain small kernels.

The remainder of this chapter studies techniques for developing kernelization algorithms that produce small kernels. We illustrate these techniques using three problems as examples: vertex cover, maximum satisfiability, and cluster editing.

• In Section 15.2, we discuss basic reduction rules to obtain polynomial kernels for the vertex cover and cluster editing problem.

• In Section 15.3, we discuss the crown reduction technique as a method for constructing a small kernel for the vertex cover and maximum satisfiability problems. A crown is a particular subgraph structure to be found in a graph. For the vertex cover problem, it will be relatively obvious that this technique can be used to construct a small kernel. For the maximum satisfiability problem, we first need to translate the given Boolean formula into a graph that captures its structure, and then the crown reduction technique applied to this graph helps us build a small kernel for the maximum satisfiability problem.

• In Section 15.4, we show how to use linear programming to construct small problem kernels. For this to be a proper kernelization procedure, which is required to run in polynomial time, we need to use a polynomial-time algorithm for solving the linear program, that is, not the Simplex Algorithm, at least in theory. We illustrate this technique using the vertex cover problem as an example.

• We conclude this chapter by discussing, in Section 15.5, how to exploit the relationship between matchings and vertex covers to obtain a linear-size kernel for the vertex cover problem. This kernel has the same size as the kernel we obtain via linear programming, but it is desirable to obtain this kernel using purely combinatorial techniques, without relying on the heavy machinery of a polynomial-time LP solver.