Diminishable parameterized problems and strict polynomial kernelization

Abstract

Kernelization – a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems – plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of $NP ⊈ coNP / poly$ . In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Müller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of $P \neq NP$ , an assumption being weaker than the assumption of $NP ⊈ coNP / poly$ . Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter.

Keywords

NP-hard problems parameterized complexity kernelization lower bounds polynomial-time data reduction Exponential Time Hypothesis

1. Introduction

Kernelization is one of the most fundamental concepts in the field of parameterized complexity analysis. Given an instance $(x, k) \in {0, 1}^{*} \times N$ of some parameterized problem $L \subseteq {0, 1}^{*} \times N$ (we assume the parameter from $N$ to be encoded in unary), a kernelization for L produces in polynomial time an instance $(x^{'}, k^{'})$ satisfying: $(x^{'}, k^{'}) \in L ⟺ (x, k) \in L$ and $| x^{'} | + k^{'} ⩽ f (k)$ for some fixed computable function $f (k)$ . In this way, kernelization can be thought of as a preprocessing procedure that reduces an instance to its “computationally hard core” (i.e., the kernel). The function $f (k)$ is accordingly called the size of the kernel, and it is typically the measure that one wishes to minimize. Kernelization is a central concept in parameterized complexity not only as an important algorithmic tool, but also because it provides an alternative definition of fixed-parameter tractability (FPT) [9,22]: A parameterized problem is solvable in $f (k) \cdot | x |^{O (1)}$ time (that is, it is fixed-parameter tractable) if and only if it has a kernel of size $g (k)$ for some arbitrary computable functions f and g only depending on the parameter k. An algorithm with running time $f (k) \cdot | x |^{O (1)}$ for a parameterized problem L implies that L has a kernel of size $f (k)$ , but in the converse direction one cannot always take the same function f. For example, the NP-complete graph problem Vertex Cover parameterized by the solution size k has a $2 k$ -vertex kernel [11], but an algorithm running in $2 k \cdot | x |^{O (1)}$ time for the problem obviously would imply $P = NP$ . The goal of minimizing the size of the problem kernel leads to the question of what is the kernel with the smallest size one can obtain in polynomial time for a given problem. In particular, do all fixed-parameter tractable problems have small kernels, say, of linear or polynomial size?

The latter question was answered negatively by Bodlaender et al. [7] who used a lemma of Fortnow and Santhanam [30] to show that various FPT problems, e.g., Path parameterized by the solution size, do not admit a polynomial-size kernel (or polynomial kernel for short) unless $NP \subseteq coNP / poly$ (which implies a collapse in the Polynomial Hierarchy to its third level). This led to the exclusion of polynomial kernels for various other problems, and the framework of Bodlaender et al. has been extended in several directions [38]. Regardless, all of these extensions rely on the assumption that $NP ⊈ coNP / poly$ , an assumption that while widely believed in the community, is a much stronger assumption than $P \neq NP$ .

Throughout the years, researchers have considered different variants of kernelization such as fidelity-preserving preprocessing [24], partial kernelization [3], lossy kernelization [43], and Turing kernelization [6,45]. In this paper, we consider a variant which has been considered previously quite a bit,1

¹
We note that this was the first definition of kernelization [20,22] and can still be found as an alternative definition for kernelization in the literature (e.g., [41,47]).

which is called proper kernelization [1] or strict kernelization [13]:

Definition 1 (Strict Kernel).

A strict kernelization for a parameterized problem L is a polynomial-time algorithm that on input $(x, k) \in {0, 1}^{*} \times N$ outputs $(x^{'}, k^{'}) \in {0, 1}^{*} \times N$ , the strict kernel, satisfying:

$(x, k) \in L ⟺ (x^{'}, k^{'}) \in L$ ,

$| x^{'} | ⩽ f (k)$ for some function f, and

$k^{'} ⩽ k + c$ for some constant $c ⩾ 0$ .

We say that L admits a strict polynomial kernelization if

f (k) \in k^{O (1)}

Thus, a strict kernelization is a kernelization that does not increase the output parameter $k^{'}$ by more than an additive constant. While the term “strict” in the definition above makes sense mathematically, it is actually quite harsh from a practical perspective. Indeed, most of the early work on kernelization involved applying so-called data reduction rules that rarely ever increase the parameter value (see, e.g., the surveys [32,38]). Furthermore, strict kernelization is clearly preferable to kernelizations that increase the parameter value in a dramatic way: Often a fixed-parameter algorithm on the resulting problem kernel is applied, whose running time highly depends on the value of the parameter, and so a kernelization that substantially increases the parameter value might in fact be useless. Finally, the equivalence with FPT is preserved: A parameterized problem is solvable in $f (k) \cdot | x |^{O (1)}$ time if and only if it has a strict kernel of size $g (k)$ (where f and g are some computable functions) [13, Proposition 3.2].

Chen et al. [13] showed that Rooted Path, the problem of finding a simple path of length k in a graph that starts from a prespecified root vertex, parameterized by k has no strict polynomial kernel unless $P = NP$ . They also showed a similar result for CNF-Sat parameterized by the number of variables. Cygan et al. [16] proved that unless $P = NP$ , Edge Clique Cover2

²
Edge Clique Cover is the problem of, given an undirected graph G and an integer k, deciding whether all edges of G can be covered by k subgraphs of G each forming a clique.

when parameterized by the number k of cliques admits no kernel of subexponential size. These results seemingly are the only known polynomial kernel lower bounds that rely on the assumption of

P \neq NP

(see Chen et al. [10] for a few linear lower bounds that also rely on

P \neq NP

).3

Note that since most FPT problems that have been studied are NP-complete with their decision versions, this is in a sense the most natural and plausible assumption one can make for the non-existence of polynomial kernels.

The goal of our work is to show that Chen et al.’s [13] framework applies for more problems and is easy to extend.

Our results. We build on the work of Chen et al. [13], and further develop and widen the framework they presented for excluding strict polynomial kernels. Using this extended framework, we show that several natural parameterized problems in FPT have no strict polynomial kernels under the assumption that $P \neq NP$ . The main result of our work is given in Theorem 1 below. Note that we use the brackets in the problem names to denote the parameter under consideration.4

⁴

For a complete list of problem definitions see Appendix x.

Theorem 1.

Unless $P = NP$ , none of the following fixed-parameter tractable problems admits a strict polynomial kernel:

Clique $(Δ)$ , Clique $(tw)$ , Clique $(bw)$ , Clique $(vs)$ , and Clique $(cw)$ ;

Biclique $(Δ)$ , Biclique $(tw)$ , Biclique $(bw)$ , Biclique $(vs)$ , and Biclique $(cw)$ ;

Terminal Steiner Tree $(k + | T |)$ ;

Multicolored Path $(k)$ , Multicolored Path $(k log n)$ , and Colorful Graph Motif $(k)$ ;

Multi-Component Annotated Defensive Alliance $(k)$ and Multi-Component Annotated Vertex Cover $(k)$ ;

Short NTM Computation $(k + | Σ |)$ , Short NTM Computation $(k + | Q |)$ , and Short Binary NTM Computation $(k)$ .

(Herein, k denotes the solution size, n, Δ, tw, bw, vs, and cw denote the number of vertices, the maximum vertex degree, the treewidth, bandwidth, vertex separation number, and cutwidth of the graph, respectively, T denotes the set of terminals,

| Σ |

denotes the alphabet size, and

| Q |

denotes the number of states.)

We give formal definitions of each of these parameterized problems and the used parameters in the following sections. For now, let us mention that several of these problems play prominent roles in previous kernelization lower bound papers. For instance, Multicolored Path $(k)$ is a WK[1]-complete problem [33]. The Colorful Graph Motif problem has been used to show that several problems in degenerate graphs have no polynomial kernels unless $NP ⊈ coNP / poly$ [17].

Finally, we also explore how “tight” the concept of strict polynomial kernels is. We study “less” strict kernels, so-called semi-strict kernels, where we allow an increase of the parameter by a constant times the input parameter. We prove a modification of the lower bound framework behind Theorem 1 for these “less” strict polynomial kernels, and apply it for two parameterized problems. In contrast, employing the Exponential Time Hypothesis (ETH), we conclude that we often cannot hope for significantly relaxing the concept of strict kernelization to achieve a comparable list of such analogous kernel lower bounds under $P \neq NP$ . We remark that our modified framework was recently applied [29] for proving the first direct kernelization lower bounds for polynomial-time solvable problems, thus contributing to the recently established “FPT in P” program [31].

The main concept behind the new proof framework is that of a parameter diminisher: an algorithm that in polynomial time decreases the parameter value of any given instance by at least one. This concept was first defined by Chen et al. [12,13] who called it a parameter-decreasing polynomial self-reduction. It is not difficult to show that the existence of a parameter diminisher and a strict polynomial kernel for an NP-hard parameterized problem implies $P = NP$ . As we will show, there are numerous natural diminishable problems; and excluding strict polynomial kernelization is comparatively simple for these problems. We remark that for the problems we discuss in this paper, one can exclude polynomial kernels under the assumption that $NP ⊈ coNP / poly$ using the framework of Bodlaender et al. [7]. Our results base on a weaker assumption, but exclude a more restricted version of polynomial kernels. On the contrary, Bodlaender et al.’s framework excludes a more general version of polynomial kernels but requires a stronger assumption. Hence, our results are incomparable with the existing no-polynomial-kernel results. However, the new framework provides a simpler methodology and directly connects the exclusion of strict polynomial kernels to the assumption that $P \neq NP$ .

Outline. The paper is organized as follows. In Section 2 we present the basic framework of Chen et al. [13], and further develop and widen it so that we have all necessary tools for proving Theorem 1. In particular, we formally define the concept of parameter diminisher and diminishable problems. In Section 3, we provide our list of problems without strict polynomial kernels, essentially proving Theorem 1. In Section 4 we investigate the effect of going from strict polynomial kernels (parameter may only increase by an additive constant) to semi-strict polynomial kernels (parameter may increase by a constant factor). We see that only few problems so far allow for this while we also show that often the corresponding “strong diminishers” (which would yield semi-strict polynomial kernels) do not exist unless the ETH breaks. We conclude in Section 5.

Preliminaries. We use basic notation from parameterized complexity [15,21,28,44] and graph theory [19]. Let $G = (V, E)$ be an undirected graph. For a vertex set $W \subseteq V$ , let $G - W : = (V ∖ W, {e \in E ∣ e \cap W = \emptyset})$ . If $W = {v}$ , then we write $G - v$ instead of $G - {v}$ . Furthermore, we denote by $G [W] : = G - (V ∖ W)$ the induced subgraph on vertices W. For a vertex $v \in V$ , we denote by $N_{G} (v) : = {w \in V ∣ {v, w} \in E}$ the neighborhood of v in G. We denote by log the logarithm with base two (if not specified differently). We denote by $[ℓ]$ , $ℓ \in N$ , the set ${1, \dots, ℓ}$ . For an algorithm $A$ on input x, we denote by $A^{c} = A (\dots A (A (x)) \dots)$ , where $A$ appears $c ⩾ 1$ times on the right-hand side of the equation.

2. Framework

In this section we present the general framework used throughout the paper. Firstly, we define the central notion of a parameter diminisher referring to parameter decreasing polynomial reduction introduced by Chen et al. [13].

Definition 2 (Parameter Diminisher).

A parameter diminisher for a parameterized problem L is a polynomial-time algorithm that maps instances $(x, k) \in {0, 1}^{*} \times N$ to instances $(x^{'}, k^{'}) \in {0, 1}^{*} \times N$ such that

$(x, k) \in L if and only if (x^{'}, k^{'}) \in L$ and

$k^{'} < k$ .

Thus, a parameter diminisher is an algorithm that is able to decrease the parameter of any given instance of a parameterized problem L in polynomial time. The algorithm is given freedom in that it can produce a completely different instance, as long as it is an equivalent one (with respect to L) and has a smaller parameter value. Note that, by definition, the parameter in a parameterized problem is a natural number, and thus the difference between the obtained parameter and the parameter in the input instance is at least one. We call a parameterized problem L diminishable if there is a parameter diminisher for L. The following theorem was proved first by Chen et al. [13], albeit for slightly weaker forms of diminisher and strict polynomial kernels.

Theorem 2 ([13]).

Let L be a parameterized problem such that its unparameterized version is NP-hard and ${(x, k) \in L ∣ k ⩽ c} \in P$ , for some constant c. If L is diminishable and admits a strict polynomial kernel, then $P = NP$ .

The idea behind Theorem 2 is to repeat the following two procedures until the parameter value drops below c (see Fig. 1 for an illustration). First, apply the parameter diminisher a constant number of times so that when, second, the strict polynomial kernelization is applied, the parameter value is decreased. The strict polynomial kernelization keeps the instances small, hence the whole process runs in polynomial time.

The following type of reductions, which do not increase the parameter value and run in polynomial time, allow for transferring diminishability from one parameterized problem to another.

Definition 3 (Parameter-Constant-Increasing Reduction).

Given two parameterized problems L with parameter k and $L^{'}$ with parameter $k^{'}$ , a parameter-constant-increasing reduction from L to $L^{'}$ is a polynomial-time algorithm that maps each instance $(x, k)$ of L to an instance $(x^{'}, k^{'})$ of $L^{'}$ such that

$(x, k) \in L ⟺ (x^{'}, k^{'}) \in L^{'}$ , and

$k^{'} ⩽ k + c$ for some constant $c ⩾ 0$ .

Note that to transfer diminishability, we need parameter-constant-increasing reductions between two parameterized problems in both directions – a crucial difference to other reduction-based hardness results.

Figure 1.

Illustration for the proof of Theorem 2 with an input instance $(x, k)$ . Herein, $K$ denotes the strict kernelization with additive constant d and $D$ denotes the parameter diminisher, respectively. We represent each instance by boxes: the size of a box symbolizes the size of the instance or the value of the parameter (each dashed box refers to k).

Lemma 1.

Let $L_{1}$ and $L_{2}$ be two parameterized problems such that there are parameter-constant-increasing reductions from $L_{1}$ to $L_{2}$ and from $L_{2}$ to $L_{1}$ . Then $L_{1}$ is diminishable if and only if $L_{2}$ is diminishable.

Proof.

Let $L_{1}$ with parameter $k_{1}$ and $L_{2}$ with parameter $k_{2}$ be two parameterized problems. Let $A_{1}$ and $A_{2}$ be parameter-constant-increasing reductions from $L_{1}$ to $L_{2}$ with constant $c_{1}$ and from $L_{2}$ to $L_{1}$ with constant $c_{2}$ , respectively. Let $D_{2}$ be a parameter diminisher for $L_{2}$ . Let $(x_{1}, k_{1})$ be an arbitrary instance of $L_{1}$ .

Apply $A_{1}$ to $(x_{1}, k_{1})$ to obtain the instance $(x_{2}, k_{2})$ of $L_{2}$ with $k_{2} ⩽ k_{1} + c_{1}$ . Next, apply $D_{2}$ to $(x_{2}, k_{2}) (c_{1} + c_{2} + 1)$ -times to obtain the instance $(x_{2}^{'}, k_{2}^{'})$ of $L_{2}$ with $k_{2}^{'} < k_{2} - c_{1} - c_{2} ⩽ k_{1} - c_{2}$ . Finally, apply $A_{2}$ to $(x_{2}^{'}, k_{2}^{'})$ to obtain the instance $(x_{1}^{'}, k_{1}^{'})$ of $L_{1}$ with $k_{1}^{'} ⩽ k_{2}^{'} + c_{2} < k_{1}$ . As $k_{1}^{'} < k_{1}$ , the above combination of $A_{1}$ , $D_{2}$ , and $A_{2}$ forms a parameter diminisher for $L_{1}$ . To get the reverse direction, exchange the roles of $L_{1}$ and $L_{2}$ . □

Parameter-decreasing branching and strict composition. To construct parameter diminishers, it is useful to follow a “branch and compose” technique: Herein, first branch into several subinstances of the input instance while decreasing the parameter value in each, and then compose the subinstances into one instance without increasing the parameter value by more than an additive constant. We first give the definitions of parameter-decreasing branching rule and strict composition, and then show that both combined form a parameter diminisher.

Branching rules are highly common in parameterized algorithm design, and they are typically deployed when using depth-bounded search-trees or related techniques. Roughly speaking, in a parameter-decreasing branching rule one reduces the problem instance to several problem instances each with smaller parameters such that at least one of these new instances is a Yes-instance if and only if the original instance is a Yes-instance.

Definition 4 (Parameter-Decreasing Branching Rule).

A parameter-decreasing branching rule for a parameterized problem L is a polynomial-time algorithm that on input $(x, k) \in {0, 1}^{*} \times N$ outputs a sequence of instances $(y_{1}, k^{'}), \dots, (y_{t}, k^{'}) \in {0, 1}^{*} \times N$ such that

$(x, k) \in L ⟺ (y_{i}, k^{'}) \in L$ for some $i \in [t]$ and

$k^{'} < k$ .

Composition is the core concept behind the standard kernelization lower bound framework introduced by Bodlaender et al. [7]. Here we use a more restrictive notion of this concept, where the parameter in the output instance is not allowed to increase by more than an additive constant to the input parameter:

Definition 5 (Strict Composition).

A strict composition for a parameterized problem L is an algorithm that receives as input t instances $(x_{1}, k), \dots, (x_{t}, k) \in {0, 1}^{*} \times N$ , and outputs in polynomial time a single instance $(y, k^{'}) \in {0, 1}^{*} \times N$ such that

$(y, k^{'}) \in L ⟺ (x_{i}, k) \in L$ for some $i \in {1, \dots, t}$ and

$k^{'} ⩽ k + c$ for some constant $c ⩾ 0$ .

If we now combine a parameter-decreasing branching rule with a strict composition, then we get a parameter diminisher.

Lemma 2.
Let L be a parameterized problem. If L admits a parameter-decreasing branching rule and a strict composition, then it is diminishable.
Proof.
Let $(x, k)$ be an instance of a parameterized problem L of size n, c be the constant associated with a strict composition for L, and the number of instances computed by the parameter-decreasing branching rule be in $O (n^{d})$ for some constant $d \in N$ . We recursively apply the parameter-decreasing branching rule for L $c + 1$ times to produce $O (n^{d^{'}})$ instances $(x_{i}, k^{})$ , with constant $d^{'} ⩽ (c + 1) d^{c + 1}$ . Note that in each application of the parameter-decreasing branching rule the parameter is decreased at least by one, and hence $k^{} < k - c$ . The strict composition, receiving $O (n^{d^{'}})$ instances, produces an instance $(y, k^{'})$ with $k^{'} ⩽ k^{} + c < k$ of L which is a Yes-instance if and only if $(x, k)$ is a Yes-instance. Hence, the whole procedure is a parameter diminisher for L. □
Remark 1.
Lemma 2 also holds true if we require in Definitions 4 and 5 that the equivalence holds for all $i \in [t]$ . That is, for parameter-decreasing branching rule we replace (i) by “ $(x, k) \in L ⟺ (y_{i}, k^{'}) \in L$ for all $i \in [t]$ ”, and for strict composition we replace (i) by “ $(y, k^{'}) \in L ⟺ (x_{i}, k) \in L$ for all $i \in [t]$ ”.

As an example application of Lemma 2 above, we consider the parameter diminisher for the Rooted Path $(k)$ problem due to Chen et al.* [13]. In this problem we are given an undirected graph $G = (V, E)$ , a distinguished vertex $r \in V$ , and an integer k, and our goal is to determine whether there exists a simple path in G of length k that starts at r. Let $v_{1}, \dots, v_{t}$ be the neighbors of r in G. The parameter-decreasing branching rule for Rooted Path $(k)$ constructs from $(G, r, k)$ the set of instances $(G - r, v_{1}, k - 1), \dots, (G - r, v_{t}, k - 1)$ . A strict composition for Rooted Path $(k)$ takes as input the instances $(G_{1}, r_{1}, k), \dots, (G_{t}, r_{t}, k)$ and constructs the instance $(G^{'}, r, k + 1)$ , where $G^{'}$ is the graph obtained by taking the disjoint union of all $G_{i}$ s and making all their roots adjacent to a new root vertex r. Combining these two algorithms – the parameter-decreasing branching rule and the strict composition – gives the parameter diminisher for Rooted Path $(k)$ .

On the exclusion of non-uniform kernelization algorithms. The presented framework can be easily adapted to exclude different forms of strict kernelizations. As our example, we show that the framework can be used to exclude strict polynomial kernels computed in non-uniform polynomial time (the corresponding complexity class is called $P / poly$ ) under the assumption that $NP ⊈ P / poly$ .
Definition 6 (Non-Uniform Strict Kernel).

A non-uniform strict kernelization for a parameterized problem L is a non-uniform polynomial-time algorithm that on input instance $(x, k) \in {0, 1}^{*} \times N$ outputs an instance $(x^{'}, k^{'}) \in {0, 1}^{*} \times N$ , the strict kernel, satisfying:

$(x, k) \in L ⟺ (x^{'}, k^{'}) \in L$ ,

$| x^{'} | ⩽ f (k)$ , for some function f, and

$k^{'} ⩽ k + c$ , for some constant c.

We say that L admits a non-uniform strict polynomial kernelization if

f (k) \in k^{O (1)}

Proposition 1.
Let L be a parameterized problem such that its unparameterized version is NP-hard and we have that ${(x, k) \in L ∣ k ⩽ c} \in P / poly$ , for some constant c. If L is diminishable and admits a non-uniform strict polynomial kernel, then $NP \subseteq P / poly$ .
Proof.
Let L be a parameterized problem whose unparameterized version is NP-hard and where it holds that ${(x, k) \in L ∣ k ⩽ c} \in P / poly$ , for a constant $c ⩾ 1$ . Let $D$ be a parameter diminisher for L such that $k^{'} ⩽ k - 1$ with $(x^{'}, k^{'}) = D (x, k)$ and let $A$ be a non-uniform strict polynomial kernelization for L with constant $c_{a} > 1$ . We show that we can solve any instance $(x, k)$ of L, with k being the parameter, in non-uniform polynomial time. Let $(x, k)$ be an instance of L. Apply $D$ on $(x, k)$ exactly $c_{r} : = ⌈ (c_{a} + 1) ⌉$ times to obtain an equivalent instance $D^{c_{r}} (x, k) = (x^{'}, k^{'})$ with $k^{'} ⩽ k - c_{r} < k - c_{a}$ . Observe that the size of $| (x^{'}, k) |$ is still polynomial in $| (x, k) |$ as $c_{r}$ is a constant. Next, apply $A$ on $(x^{'}, k^{'})$ to obtain an equivalent instance $(x^{″}, k^{″})$ with $| (x^{″}, k^{″}) | ⩽ k^{' c^{'}}$ , where $c^{'} ⩾ 1$ , and $k^{″} ⩽ k^{'} + c_{a} < k$ ; we explain how to get the advice for $A$ in the second half of the proof. Repeating the described procedure at most k times produces an instance $(y, 1)$ of L, solvable in non-uniform polynomial time.

In the remainder of the proof, we explain how to obtain the advices for the applications of the non-uniform strict polynomial kernelization. Given any instance size n, we claim that for all instances $(x, k) \in L$ with $| (x, k) | = n$ , we can upper-bound the sizes of all instances $(x^{}, k^{})$ for which a non-uniform strict polynomial kernel needs to be computed in the above described procedure by a polynomial in n. Let the running time of the diminisher $D$ be $O (n^{c^{″}})$ . It follows that $| (x^{'}, k^{'}) | ⩽ c_{O} \cdot n^{c^{″} \cdot c_{r}}$ , where $(x^{'}, k^{'}) = D^{c_{r}} (x, k)$ and $c_{O}$ is the constant hidden in the O-notation. Furthermore, we have that the size of all subsequent instances the diminisher sequence $D^{c_{r}}$ is applied to is smaller than $k^{c^{'}}$ . Thus, the sizes of all instances $(x^{}, k^{})$ for which a non-uniform strict polynomial kernel needs to be computed can be upper-bounded by $c_{O} \cdot n^{c^{'} \cdot c^{″} \cdot c_{r}}$ . A list containing all advices for all instance sizes smaller or equal to this bound has polynomial length, since all advices have polynomial length. Hence, the overall procedure can take that list as an advice and use it as a look-up table for the advices needed to apply the non-uniform strict polynomial kernels. □

We remark that if $NP \subseteq P / poly$ , then the Polynomial Hierarchy collapses to its second level [36] (notably, $NP \subseteq coNP / poly$ implies a collapse in the Polynomial Hierarchy to its third level).
3. Problems without strict polynomial kernels

In this section we prove Theorem 1 based on several propositions to follow. We present parameter diminishers for most problems mentioned in Theorem 1, and for some problems we show that they do not admit strict polynomial kernels (unless $P = NP$ ) using parameter-non-increasing reductions. Note that all parameterized problems we consider are either known to be in FPT, or we prove containment in FPT. This section is segmented into five parts, following the order in which the problems are stated in Theorem 1. We study in Section 3.1 Clique and Biclique, in Section 3.2 Terminal Steiner Tree, in Section 3.3 Multicolored Path and Colorful Graph Motif, in Section 3.4 Multi-Component Annotated Π, and finally in Section 3.5 Short NTM Computation and Short Binary NTM Computation.

3.1. Clique and biclique

We begin with the Clique problem: Given an undirected graph $G = (V, E)$ and an integer k, determine whether there exist k vertices $v_{1}, \dots, v_{k} \in V$ such that ${v_{i}, v_{j}} \in E$ for all $1 ⩽ i < j ⩽ k$ . Since Clique $(k)$ is W[1]-complete, we focus on other parameterizations of Clique that are contained in FPT, for instance the maximum degree Δ of the input graph, where Clique has a simple FPT algorithm: Exhaustively search the closed neighborhood of each vertex individually. Other parameterizations include treewidth $tw = tw (G)$ , bandwidth $bw = bw (G)$ , vertex separation $vs = vs (G)$ , and the cutwidth $cw = cw (G)$ of the input graph. Our first main result of this section is the following.

Proposition 2.
Clique $(Δ)$ , Clique $(tw)$ , Clique $(bw)$ , Clique $(vs)$ , and Clique $(cw)$ are diminishable.

Observe that if $cw ⩽ c$ for some constant, then $Δ ⩽ 2 c$ , and Clique is in FPT when parameterized by the maximum degree. We prove Proposition 2 via the “branch and compose” technique (see Section 2). For the parameter-branching rule, the following is the underlying construction.
Construction 1.
Let $G = (V, E)$ be a graph. For each $v \in V$ , construct a graph $G_{v}$ , where $G_{v}$ denotes the subgraph of G induced by the open neighborhood of v, that is, $G_{v} = G [N (v)]$ . Let $G (G) : = {G_{v} ∣ v \in V}$ denote the set of all such graphs.

In what follows, for each parameter stated in Proposition 2 we give its definition and prove that its value decreases by at least one in each graph in the set output by Construction 1. Note that for every graph the cutwidth cw upper-bounds each of the other parameters listed in Proposition 2 (observe that $bw ⩽ cw$ ; for the remaining relations, refer to Sorge and Weller [46]). However, we point out that diminishability of a parameter p does not necessarily transfer to parameters which are upper bounded by p. We begin with the maximum vertex degree Δ of the input graph.
Observation 1.
Let G be a graph and $G (G)$ denote the set obtained from applying Construction 1 to G. Then ${max}_{H \in G (G)} Δ (H) < Δ (G)$ .
Proof.
Observe that for all $v \in V (G)$ , $G_{v} = G [N_{G} [v]] - v$ , and hence we have that $Δ (G_{v}) = Δ (G [N_{G} [v]]) - 1 < Δ (G)$ . □

Given a graph $G = (V, E)$ , a tuple $X = (T, {(B_{α})}_{α \in V (T)})$ consisting of a tree T and subsets $B_{α} \subseteq V$ for all $α \in V (T)$ is a tree decomposition of G if the following holds: (i) $V = ⋃_{α \in V (T)} B_{α}$ , (ii) for all $e \in E$ there exists an $α \in V (T)$ such that $e \subseteq B_{α}$ , and (iii) for all $v \in V$ , the induced graph $T [{α \in V (T) ∣ v \in B_{α}}]$ is a tree. The width of X is $w (X) : = {max}_{α \in V (T)} {| B_{α} | - 1}$ . The treewidth of G is the minimum width over all tree decompositions of G.
Lemma 3.
Let G be a graph and $G (G)$ denote the set of graphs obtained from applying Construction 1 to G. Then ${max}_{H \in G (G)} tw (H) < tw (G)$ .
Proof.
For all $v \in V$ , denote by $G_{v}^{'}$ the graph $G [N_{G} [v]]$ . Note that for all $v \in V$ , as $G_{v}^{'} \subseteq G$ , we have that $tw (G_{v}^{'}) ⩽ tw (G)$ . Let $X = (T, {(B_{α})}_{α \in V (T)})$ denote a tree decomposition of G of width $tw (G)$ . Note that $X_{v}^{'} = (T, {(B_{α}^{'})}_{α \in V (T)})$ , where $B_{α}^{'} : = B_{α} \cap N_{G} [v]$ for all $α \in V (T)$ , is a tree decomposition of $G_{v}^{'}$ of width at most $tw (G)$ [19]. We claim that the tree decomposition $X_{v} = (T, {(B_{α}^{})}_{α \in V (T)})$ , where $B_{α}^{} : = B_{α} \cap N_{G} (v)$ for all $α \in V (T)$ , of $G_{v}$ has width at most $w (X_{v}^{'}) - 1$ . Suppose not, that is, there is an $α \in V (T)$ such that $| B_{α}^{} | = w (X_{v}^{'}) + 1$ (note that $B_{α}^{'} = B_{α}^{}$ , and hence $v \notin B_{α}^{'}$ ). Let $β \in V (T)$ denote the node in T closest to α whose bag contains v in $X_{v}^{'}$ , that is, $v \in B_{β}^{'}$ and ${dist}_{T} (α, β) = {min}_{β^{'} \in V (T) : v \in B_{β^{'}}^{'}} {dist}_{T} (α, β^{'})$ . Since v is adjacent to each vertex in $N_{G} (v)$ , it holds true that for each $w \in B_{α}^{'}$ , there is a $γ \in V (T)$ such that ${v, w} \subseteq B_{γ}^{'}$ . By property (iii) of tree decompositions and the choice of node β, it follows that $B_{α}^{'} \subseteq B_{β}^{'}$ . Since $v \in B_{β}^{'}$ , we have $| B_{α}^{'} | < | B_{β}^{'} |$ , contradicting the choice of α. Altogether, we have $tw (G_{v}) ⩽ w (X_{v}) < w (X_{v}^{'}) ⩽ tw (G)$ . □

The bandwidth of a graph $G = (V, E)$ is defined as the minimum value of ${max}_{{u, w} \in E} | σ (u) - σ (w) |$ over all bijections $σ : V \to {1, \dots, | V |}$ (also referred to as vertex-orderings).
Lemma 4.
Let G be a graph and $G (G)$ denote the set of graphs obtained from applying Construction 1 to G. Then ${max}_{H \in G (G)} bw (H) < bw (G)$ .
Proof.
For all $v \in V$ , denote by $G_{v}^{'}$ the graph $G [N_{G} [v]]$ . Note that for all $v \in V$ , as $G_{v}^{'} \subseteq G$ , we have that $bw (G_{v}^{'}) ⩽ bw (G)$ [18]. Let $σ : V (G_{v}^{'}) \to {1, \dots, | V (G_{v}^{'}) |}$ be a vertex-ordering for $G_{v}^{'}$ with $bw (G_{v}^{'}) = {max}_{{u, w} \in E (G_{v}^{'})} | σ (u) - σ (w) |$ . Let $σ^{'}$ denote the vertex-ordering obtained from σ such that $σ^{'} (w) = σ (w)$ if $σ (w) < σ (v)$ , and $σ^{'} (w) = σ (w) - 1$ if $σ (w) > σ (v)$ for all $w \in N_{G} (v)$ . It follows that for every ${x, y} \in E (G_{v}^{'})$ with $σ (x) < σ (v) < σ (y)$ , it holds true that $| σ^{'} (x) - σ^{'} (y) | = | σ (x) - σ (y) | - 1$ . Observe that since v is adjacent to all vertices in $N_{G} (v)$ , for every ${x, y} \in E (G_{v}^{'})$ with $v \notin {x, y}$ and $σ (y) - σ (x) = {max}_{{u, w} \in E (G_{v}^{'})} | σ (u) - σ (w) |$ it holds true that $σ (x) < σ (v) < σ (y)$ . Hence $bw (G_{v}) = bw (G_{v}^{'}) - 1 < bw (G)$ . □

The vertex separation of a graph $G = (V, E)$ is defined as the minimum value of ${max}_{1 ⩽ i ⩽ | V |} | F_{σ, i} |$ over all vertex-orderings $σ : V \to {1, \dots, | V |}$ , where $F_{σ, i} : = {u \in V ∣ σ (u) ⩽ i \land \exists {u, w} \in E : σ (w) > i}$ . Note that for every graph the vertex separation number and the pathwidth are equal [37].
Lemma 5.
Let G be a graph and $G (G)$ denote the set of graphs obtained from applying Construction 1 to G. Then ${max}_{H \in G (G)} vs (H) < vs (G)$ .
Proof.
For all $v \in V$ , denote by $G_{v}^{'}$ the graph $G [N_{G} [v]]$ . Note that for all $v \in V$ , as $G_{v}^{'} \subseteq G$ , we have that $vs (G_{v}^{'}) ⩽ vs (G)$ [18]. Let $σ : V (G_{v}^{'}) \to {1, \dots, | V (G_{v}^{'}) |}$ be a vertex-ordering for $G_{v}^{'}$ with $vs (G_{v}^{'}) = {max}_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | F_{σ, i} |$ such that $σ (v)$ is smallest among all such orderings. Define the set $I : = \arg \max_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | F_{σ, i} |$ . We claim that $σ (v) ⩽ i$ for all $i \in I$ .

Suppose not, that is, there is an $i \in I$ such that $σ (v) > i$ . Let $j \in I$ denote the largest index in I such that $σ (v) > j$ . Observe that $j = σ (v) - 1$ , as otherwise $| F_{σ, j} | < | F_{σ, σ (v) - 1} |$ since all vertices in $V (G_{v}^{'}) ∖ {v}$ are adjacent to v. Let $w \in V (G_{v}^{'})$ denote the vertex with $σ (w) = j$ . Consider the vertex-ordering $σ_{v w}$ with $σ_{v w} (v) = w$ , $σ_{v w} (w) = v$ , and $σ_{v w} (u) = u$ for all $u \in V (G_{v}^{'}) ∖ {v, w}$ . Observe that $| F_{σ^{'}, j} | ⩽ | F_{σ, j} |$ since every vertex u with $σ (u) ⩽ j$ is adjacent with v. Moreover, for all $i \in {1, \dots, | V (G_{v}^{'}) |} ∖ {j}$ it holds true that $| F_{σ_{v w}, i} | = | F_{σ, i} |$ since ${u \in V (G_{v}^{'}) ∣ σ (u) ⩽ i} = {u \in V (G_{v}^{'}) ∣ σ_{v w} (u) ⩽ i}$ . It follows that $σ_{v w}$ is a vertex-ordering for $G_{v}^{'}$ with $vs (G_{v}^{'}) = {max}_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | F_{σ_{v w}, i} |$ such that $σ_{v w} (v) < σ (v)$ , contradicting the choice of σ. Hence, we have that $σ (v) ⩽ i$ for all $i \in I$ .

Let $σ^{'}$ denote the vertex-ordering obtained from σ such that $σ^{'} (w) = σ (w)$ if $σ (w) < σ (v)$ , and $σ^{'} (w) = σ (w) - 1$ if $σ (w) > σ (v)$ for all $w \in N_{G} (v)$ . Since $G_{v} \subseteq G_{v}^{'}$ , we have that $| F_{σ^{'}, σ^{'} (w)} | ⩽ | F_{σ, σ (w)} |$ for all $w \in V (G_{v})$ [18]. Since for all $i \in I$ it holds true that $σ (v) ⩽ i$ , we have that $| F_{σ^{'}, σ^{'} (w)} | ⩽ | F_{σ, σ (w)} | - 1$ for all $w \in V (G_{v})$ such that there is an $i \in I$ with $σ (w) = i$ . Altogether, it follows that $vs (G_{v}) ⩽ {max}_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | F_{σ^{'}, i} | < vs (G_{v}^{'}) ⩽ vs (G)$ . □

The cutwidth of a graph $G = (V, E)$ is defined as the minimum value of ${max}_{1 ⩽ i ⩽ | V |} | E_{σ, i} |$ over all vertex-orderings $σ : V \to {1, \dots, | V |}$ , where $E_{σ, i} : = {{u, w} \in E ∣ σ (u) ⩽ i < σ (w)}$ .
Lemma 6.
Let G be a graph and $G (G)$ denote the set of graphs obtained from applying Construction 1 to G. Then ${max}_{H \in G (G)} cw (H) < cw (G)$ .
Proof.
For all $v \in V$ , denote by $G_{v}^{'}$ the graph $G [N_{G} [v]]$ . Note that for all $v \in V$ , as $G_{v}^{'} \subseteq G$ , we have that $cw (G_{v}^{'}) ⩽ cw (G)$ [18]. Let $σ : V (G_{v}^{'}) \to {1, \dots, | V (G_{v}^{'}) |}$ be a vertex-ordering for $G_{v}^{'}$ with $cw (G_{v}^{'}) = {max}_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | E_{σ, i} |$ . Let $σ^{'}$ denote the vertex-ordering obtained from σ such that $σ^{'} (w) = σ (w)$ if $σ (w) < σ (v)$ , and $σ^{'} (w) = σ (w) - 1$ if $σ (w) > σ (v)$ for all $w \in N_{G} (v)$ . Note that $σ^{'}$ is an ordering on the vertices of $G_{v}$ . Since v is adjacent to each vertex in $V (G_{v}^{'}) ∖ {v}$ , it holds that $| E_{σ^{'}, j^{'}} | ⩽ | E_{σ, j} | - 1$ for each $j \in [| V (G_{v}^{'}) |]$ and $j^{'} = j$ , if $j < σ (v)$ , and $j^{'} = j - 1$ , otherwise. It follows that $cw (G_{v}) ⩽ {max}_{1 ⩽ i ⩽ | V (G_{v}) |} | E_{σ^{'}, i} | < {max}_{1 ⩽ i ⩽ | V (G_{v}^{'}) |} | E_{σ, i} | = cw (G_{v}^{'}) ⩽ cw (G)$ . □

Construction 1 yields a parameter diminisher for parameters tw, bw, vs, cw and k. Leaving the W[1]-complete Clique $(k)$ problem aside, we prove our first main result of this section.
Proof of Proposition 2.
Let $(G = (V, E), k)$ be an instance of Clique. The following is a parameter-decreasing branching rule for $(G = (V, E), k)$ : Apply Construction 1 to G, and construct for each $G_{v} \in G (G)$ the instance $(G_{v}, k - 1)$ .

We prove that G has a clique of size k if and only if $G_{v}$ has a clique of size $k - 1$ for some $v \in V$ . Let C be a clique in G with k vertices and $v \in V (C)$ . Let $C^{'} : = C - v$ denote the clique of size $k - 1$ obtained from C by deleting v. Since for every $w \in V (C^{'})$ it holds $w \in N_{G} (v)$ , we have $C^{'} \subseteq G_{v}$ , and the claim follows. Conversely, let $v \in V$ such that $G_{v}$ contains a clique $C^{'}$ of size $k - 1$ . By construction, $v \notin V (C^{'})$ as $C^{'} \subseteq G_{v}$ , and v is adjacent to all vertices in $G_{v}$ . It follows that $C \cup {v}$ is a clique of size k in G.

Finally, due to Observation 1 and Lemmas 3 to 6, we know that in each instance the corresponding parameter value decreased.

For the composition step we take the disjoint union of all graphs. Formally, on input instances $(G_{1}, k), \dots, (G_{t}, k)$ , $t \in N$ , we compute the instance $(G_{1} ⊎ \dots ⊎ G_{t}, k)$ . Note that a graph has a clique of size k if and only if one of its connected components has a clique of size k. Moreover, for all stated parameters it holds true that their value equals the maximum value of the connected components of the input graph [14,18]. Applying Lemma 2, this completes the proof. □

Next we show that the parameter diminisher presented for Clique can be adapted to the Biclique problem: Given an undirected bipartite graph $G = (A ⊎ B, E)$ and an integer k, find k vertices $a_{1}, \dots, a_{k} \in A$ and $b_{1}, \dots, b_{k} \in B$ such that ${a_{i}, b_{j}} \in E$ for all $1 ⩽ i, j ⩽ k$ . Thus, we have our second main result of this section: Corollary 1.
Biclique $(Δ)$ , Biclique $(tw)$ , Biclique $(bw)$ , Biclique $(vs)$ and Biclique $(cw)$ are diminishable.
Proof sketch.
We only present the parameter-decreasing branching rule. The rest of the proof is analogous to the proof of Proposition 2. Let $(G = (A ⊎ B, E), k)$ be an instance of Biclique. The following is a parameter-decreasing branching rule for $(G = (A ⊎ B, E), k)$ : For each ${v, w} \in E$ , construct the instance $(G_{v, w}, k - 1)$ where $G_{v, w} : = G [(N_{G} (v) ∖ {w}) \cup (N_{G} (w) ∖ (v))]$ . □

3.2. Terminal Steiner tree

The well-known Steiner Tree problem is defined as follows: given an undirected graph $G = (V, E)$ with $V = N ⊎ T$ (T is called the terminal set) and a positive integer k, decide whether there is a subgraph $H \subseteq G$ with at most $k + | T |$ vertices such that H is a tree containing all vertices in T. In this section, we consider the variant Terminal Steiner Tree (TST) [5,40] of Steiner Tree, which additionally requires the terminal set T to be a subset of the set of leaves of the tree H. TST is proven to be NP-complete. We are not aware of any parameterized complexity study for TST. Hence, for the sake of completeness, in the following two lemmas we show that TST, when parameterized by the size $k + | T |$ of the terminal Steiner tree in question, is fixed-parameter tractable and does not admit a polynomial kernel unless $NP \subseteq coNP / poly$ .

Lemma 7.
Terminal Steiner Tree $(k + | T |)$ is fixed-parameter tractable.
Proof.
We give an FPT-reduction from TST $(k + | T |)$ to Steiner Tree $(k^{'} + | T |)$ . As Steiner Tree $(k^{'} + | T |)$ is fixed-parameter tractable [23], the claim follows.

Let $(G = (N ⊎ T, E), k)$ be an instance of TST $(k + | T |)$ . We construct an equivalent instance $(G^{'} = (N^{'} ⊎ T, E^{'}), k^{'})$ of Steiner Tree $(k^{'} + | T |)$ as follows. Let $G^{'}$ be initially a copy of G. For each $t \in T$ , apply the following. For each edge ${v, t} \in E$ , remove ${v, t}$ from $G^{'}$ and add a path of length $2 (k + | T |)$ to $G^{'}$ with endpoints v and t. Set $k^{'} = | T | \cdot (2 (k + | T |) - 1) + k$ . This finishes the reduction. Clearly, the construction can be done in FPT-time.

We show that $(G = (N ⊎ T, E), k)$ is a Yes-instance of TST $(k + | T |)$ if and only if $(G^{'} = (N^{'} ⊎ T, E^{'}), k^{'})$ is a Yes-instance of Steiner Tree $(k^{'} + | T |)$ .

(⇒) Let H be a terminal Steiner tree in G with $ℓ ⩽ k + | T |$ vertices. We construct a Steiner tree $H^{'}$ in $G^{'}$ from H with $ℓ^{'} ⩽ k^{'} + | T |$ vertices as follows. Recall that each $t \in T$ has exactly one neighbor $v_{t}$ in H. Hence, obtain $H^{'}$ by replacing for each $t \in T$ the edge ${v_{t}, t} \in E (H)$ by the path of length $2 (k + | T |)$ connecting $v_{t}$ with t. It is not difficult to see that $H^{'}$ is a Steiner tree in $G^{'}$ . Moreover, $ℓ^{'} = | V (H^{'}) | = | V (H) | + | T | (2 (k + | T |) - 1) ⩽ k + | T | + | T | (2 (k + | T |) - 1) = k^{'} + | T |$ .

(⇐) Let $H^{'}$ be a minimum Steiner tree in $G^{'}$ with $ℓ^{'} ⩽ k^{'} + | T |$ vertices. We state some first observations on $H^{'}$ . Observe that no inner vertex of the paths added in the construction step from G to $G^{'}$ is a leaf of $H^{'}$ (as otherwise $H^{'}$ is not minimum). Moreover, as $H^{'}$ contains each $t \in T$ , $H^{'}$ contains a path of length $2 (k + | T |)$ for each $t \in T$ . Suppose that there is a terminal $t \in T$ such that t is not a leaf in $H^{'}$ . Then the number of vertices of $H^{'}$ is at least $| T | + (| T | + 1) \cdot (2 (k + | T |) - 1) = | T | \cdot (2 (k + | T |) - 1) + 2 (k + | T |) - 1 = k^{'} + (k + | T |) - 1 > k^{'} + | T |$ , yielding a contradiction. Hence, each terminal $t \in T$ forms a leaf in $H^{'}$ . We show how to obtain a terminal Steiner tree H in G from $H^{'}$ with at most $k + | T |$ vertices. As each terminal $t \in T$ forms a leaf in $H^{'}$ , there is exactly one neighbor $v_{t} \in N_{G} (t)$ such that $H^{'}$ contains the path of length $2 (k + | T |)$ connecting $v_{t}$ with t. Replace for each $t \in T$ the path of length $2 (k + | T |)$ connecting $v_{t}$ with t in $H^{'}$ by the edge ${v_{t}, t} \in E$ to obtain H from $H^{'}$ . Note that H is a terminal Steiner tree. Moreover, $| V (H) | = | V (H^{'}) | - | T | \cdot (2 (k + | T |) - 1) ⩽ | T | + | T | \cdot (2 (k + | T |) - 1) + k - | T | \cdot (2 (k + | T |) - 1) = k + | T |$ . □
Lemma 8.
Unless $NP \subseteq coNP / poly$ , Terminal Steiner Tree $(k + | T |)$ does not admit a polynomial kernel.
Proof.
We give a polynomial parameter transformation from Steiner tree $(k + | T |)$ to TST $(k + | T |)$ . Let $(G = (N ⊎ T, E), k)$ be an instance of Steiner tree $(k + | T |)$ . We construct instance $(G^{'} = (N^{'} ⊎ T^{'}, E^{'}), k^{'})$ of TST $(k^{'} + | T |)$ as follows. Let $G^{'}$ be initially a copy of G. Next, for each terminal vertex $t \in T$ , add a vertex $v_{t}$ to $G^{'}$ and make it adjacent only with t. Denote by $T^{'} : = {v_{t} ∣ t \in T}$ the set of vertices added in the previous step. Set $N^{'} : = N \cup T$ and $k^{'} : = k + | T |$ . This finishes the construction of $(G^{'} = (N^{'} ⊎ T^{'}, E^{'}), k^{'})$ . We claim that $(G = (N ⊎ T, E), k)$ admits a Steiner tree of size $k + | T |$ if and only if $(G^{'} = (N^{'} ⊎ T^{'}, E^{'}), k^{'})$ admits a terminal Steiner tree of size $k^{'} + | T^{'} |$ .

(⇒) Let S be a Steiner tree in G of size $k + | T |$ . It is not difficult to see that $S^{'} : = (V (S) \cup T^{'}, E (S) \cup {{v_{t}, t} \in E (G^{'}) ∣ t \in T})$ is a terminal Steiner tree in $G^{'}$ of size $k + | T | + | T | = k^{'} + | T^{'} |$ .

(⇐) Let $S^{'}$ denote a terminal Steiner tree in $G^{'}$ of size $k^{'} + | T^{'} |$ . Note that $T^{'} \subseteq V (S)$ and as each vertex $v_{t} \in T^{'}$ has exactly one neighbor $t \in T$ , it follows that $S : = (V (S) ∖ T^{'}, E (S^{'}) ∖ {{v_{t}, t} \in E (G^{'}) ∣ t \in T})$ is a Steiner tree in G of size $k^{'} + | T^{'} | - | T^{'} | = k^{'} = k + | T |$ . □
Proposition 3.
Terminal Steiner Tree $(k + | T |)$ is diminishable.
Proof.
We present a parameter-decreasing branching rule and a strict composition for Terminal Steiner Tree $(k + | T |)$ . Together with Lemma 2, the claim then follows. Let $(G = (N ⊎ T, E), k)$ be an instance of TST $(k + | T |)$ (we can assume that G has a connected component containing T). We make several assumptions first. We can assume that $| T | ⩾ 3$ (otherwise a shortest path is the optimal solution). Additionally, we assume that for all terminals $t \in T$ it holds that $N_{G} (t) ⊈ T$ (as otherwise the instance is a No-instance and we output a trivial No-instance). Moreover, we can assume that there is no vertex $v \in N$ such that $T \subseteq N_{G} (v)$ , as otherwise we immediately output a trivial Yes-instance if $k ⩾ 1$ or a trivial No-instance otherwise.

For the parameter decreasing branching rule, select a terminal $t^{} \in T$ , and let $v_{1}, \dots, v_{d}$ denote the neighbors of $t^{}$ in $G - (T ∖ {t^{}})$ . We create d instances $(G_{1}, k - 1), \dots, (G_{d}, k - 1)$ as follows. Define $G_{i}$ , $i \in [d]$ , by $G_{i} : = G - v_{i}$ . Turn the vertices in $N_{G} (v_{i})$ in $G_{i}$ into a clique, that is, for each distinct vertices $v, w \in N_{G} (v_{i})$ add the edge ${v, w}$ if not yet present. This finishes the construction of $G_{i}$ . It is not hard to see that the construction can be done in polynomial time.

We show that G has a terminal Steiner tree of size $k + | T |$ if and only if there is an $i \in [d]$ such that $G_{i}$ admits a terminal Steiner tree of size $k - 1 + | T |$ . Suppose that G has a terminal Steiner tree H of size $k + | T |$ . As $t^{}$ is a leaf in H, there is exactly one neighbor $v_{i} \notin T$ , $i \in [d]$ , being the neighbor of $t^{}$ in H (which exists since $| T | ⩾ 3$ and $N_{G} (t) ⊈ T$ ). Let w be a neighbor of $v_{i}$ in $H - T$ (which exists since $T ⊈ N_{G} (v_{i})$ ) and let $A : = N_{H} (v_{i})$ (note that $t^{} \in A$ ). Then $H_{i}$ forms a terminal Steiner tree in $G_{i}$ , where $H_{i}$ is the tree obtained from H by deleting $v_{i}$ and connecting w with all vertices in A. Moreover, $H_{i}$ is of size $k - 1 + | T |$ .

Conversely, let $G_{i}$ admit a terminal Steiner tree $H_{i}$ of size $k - 1 + | T |$ . As $t^{}$ is a leaf in $H_{i}$ , there is exactly one vertex w being the neighbor of $t^{}$ in $H_{i}$ . We obtain a terminal Steiner tree H in G from $H_{i}$ as follows. If every edge in $H_{i}$ is also present in G, then $H : = H_{i}$ also forms a terminal Steiner tree in G. Otherwise, there is an inclusion-wise maximal edge set $E^{'} \subseteq E (H_{i})$ such that $E^{'} \cap E (G) = \emptyset$ . Observe that by construction, the set of endpoints of $E^{'}$ forms a subset of $N_{G} (v_{i})$ . Let initially H be a copy of $H_{i}$ . Delete from H all edges in $E^{'}$ , add vertex $v_{i}$ to H, and for each ${x, y} \in E^{'}$ , add the edges ${x, v_{i}}$ and ${y, v_{i}}$ . Note that H remains connected after this step, and the set of leaves remains unchanged. Finally, compute a minimum feedback edge set in H if necessary. Observe that since $V (H) = V (H_{i}) \cup {v_{i}}$ , H forms a terminal Steiner tree of size $k + | T |$ in G.

Finally, we describe the strict composition for TST $(k + | T |)$ . Given the instances $(G_{1}, k), \dots, (G_{d}, k)$ , we create an instance $(G^{'}, k)$ as follows. Let $G^{'}$ be initially the disjoint union of $G_{1}, \dots, G_{d}$ . For each $t \in T$ , identify its copies in $G_{1}, \dots, G_{d}$ , say $t_{1}, \dots, t_{d}$ , with one vertex $t^{'}$ corresponding to t. This finishes the construction of $G^{'}$ . Note that for every $i, j \in [d]$ , $i \neq j$ , any path between a vertex in $G_{i}$ and a vertex in $G_{j}$ contains a terminal vertex. Hence, any terminal Steiner tree in $G^{'}$ contains non-terminal vertices only in $G_{i}$ for exactly one $i \in [d]$ . It is not difficult to see that $(G^{'}, k)$ is a Yes-instance if and only if one of the instances $(G_{1}, k), \dots, (G_{d}, k)$ is a Yes-instance. □

3.3. Multicolored graph problems

First, we present a diminisher for the Multicolored Path $(k)$ problem: Given an undirected graph $G = (V, E)$ with a vertex coloring function $col : V \to [k]$ , determine whether there exists a simple path of length k with one vertex of each color. This problem is NP-complete as it generalizes Hamiltonian Path. Furthermore, Multicolored Path $(k)$ is fixed-parameter tractable as it can be solved in $2^{O (k)} n^{2}$ time [2]. The idea used in the parameter diminisher for Multicolored Path $(k)$ can also be applied for the Colorful Graph Motif problem, a problem with applications in bioinformatics.

Proposition 4.
Multicolored Path $(k)$ is diminishable.

We remark that the diminishability of the (uncolored) Path $(k)$ problem, asking whether a given graph contains a simple path of length k, remains open. Hence, for graph problems, a vertex-coloring seems to help to construct diminishers.
Proof.
We give a parameter-decreasing branching rule and a strict composition for Multicolored Path $(k)$ . The result then follows from Lemma 2. Let $(G = (V, E), col)$ be an instance of Multicolored Path $(k)$ . Our parameter-decreasing branching rule for $(G = (V, E), col)$ computes an instance $(G_{(v_{1}, v_{2}, v_{3})}, {col}^{'})$ for each ordered triplet $(v_{1}, v_{2}, v_{3})$ of pairwise distinct vertices of V such that $v_{1}, v_{2}, v_{3}$ forms a multicolored path in G. The graph $G_{(v_{1}, v_{2}, v_{3})}$ is constructed from G as follows: Delete from G all vertices $w \in V ∖ {v_{2}, v_{3}}$ with $col (w) \in {col (v_{1}), col (v_{2}), col (v_{3})}$ . Following this, only vertices of $k - 1$ colors remain, and $v_{2}$ and $v_{3}$ are the only vertices colored $col (v_{2})$ and $col (v_{3})$ , respectively. Then delete all edges incident with $v_{2}$ , apart from ${v_{2}, v_{3}}$ , and relabel all colors so that the image of col for $G_{(v_{1}, v_{2}, v_{3})}$ is $[k - 1]$ .

Clearly our parameter-decreasing branching rule can be performed in polynomial time. Furthermore, the parameter decreases in each output instance. We show that the first requirement of Definition 4 holds as well: Indeed, suppose that G has a multicolored path $v_{1}, v_{2}, \dots, v_{k}$ of length k. Then $v_{2}, \dots, v_{k}$ is a multicolored path of length $k - 1$ in $G_{(v_{1}, v_{2}, v_{3})}$ by construction. Conversely, suppose that there is a multicolored path $u_{2}, \dots, u_{k}$ of length $k - 1$ in some $G_{(v_{1}, v_{2}, v_{3})}$ . Then since $v_{2}$ is the only vertex of color $col (v_{2})$ in $G_{(v_{1}, v_{2}, v_{3})}$ , and since $v_{2}$ is only adjacent to $v_{3}$ , without loss of generality it must be that $u_{2} = v_{2}$ and $u_{3} = v_{3}$ . Hence, since $v_{1}$ is adjacent to $v_{2}$ in G, and no vertices of $u_{2}, \dots, u_{k}$ have color $col (v_{1})$ in G, the sequence of $v_{1}, u_{2}, \dots, u_{k}$ forms a multicolored path of length k in G.

Our strict composition for Multicolored Path $(k)$ is as follows. Given a sequence of inputs $(G_{1}, {col}_{1}), \dots, (G_{t}, {col}_{t})$ , the strict composition constructs the disjoint union G and the coloring function col of all graphs $G_{i}$ and coloring functions ${col}_{i}$ , $1 ⩽ i ⩽ t$ . Clearly, $(G, col)$ contains a multicolored path of length k if and only if there is a multicolored path of length k in some $(G_{i}, {col}_{i})$ . The result thus follows directly from Lemma 2. □
Proposition 5.
Unless $P = NP$ , Multicolored Path $(k log n)$ has no strict polynomial kernel.
Proof.
Chen et al. [13, Proposition 3.10] proved that if L is a parameterized problem which can be solved in $2^{k^{O (1)}} | x |^{O (1)}$ time, where k is the parameter and $| x |$ is the instance size, then $L (k)$ has a polynomial kernel if and only if $L (k log | x |)$ has a polynomial kernel. It is easy to verify that their proof also holds for strict polynomial kernels. Thus, as Multicolored Path $(k)$ can be solved in $2^{k^{O (1)}} n^{O (1)}$ time [2], the result follows. □

The Colorful Graph Motif problem asks, given an undirected graph $G = (V, E)$ and a vertex coloring function $col : V \to {1, \dots, k}$ , whether there exists a connected subgraph of G containing exactly one vertex of each color. Colorful Graph Motif $(k)$ is known to be fixed-parameter tractable [4]. Proposition 6.
Colorful Graph Motif $(k)$ is diminishable.
Proof.
We show that there is a parameter-decreasing branching rule and a strict composition for Colorful Graph Motif $(k)$ . Let $(G = (V, E), col)$ be an instance of Colorful Graph Motif $(k)$ . Assume that there are only edges between differently colored vertices. For each ${v, w} \in E$ , the parameter-decreasing branching rule computes an instance $(G_{{v, w}}, {col}^{'})$ where the graph $G_{{v, w}}$ is a copy of G where all vertices of colors $col (v)$ and $col (w)$ are removed. Furthermore, a new vertex $v^{⋆}$ is added with color $col (v^{⋆}) = col (v)$ and with edges to all vertices in $N (v) \cup N (w)$ that have not been removed. Clearly, $G_{{v, w}}$ only contains vertices of $k - 1$ different colors and is computable in polynomial time. Also, if G contains a colorful motif ${v_{1}, v_{2}, \dots, v_{k}}$ where, without loss of generality, ${v_{1}, v_{2}} \in E$ , then $G_{{v_{1}, v_{2}}}$ contains the colorful motif ${v^{⋆}, v_{3}, \dots, v_{k}}$ . Conversely, if a graph $G_{{v, w}}$ contains a colorful motif, then it has to contain $v^{⋆}$ since it is the only vertex of its color. Let ${v^{⋆}, v_{2}, \dots, v_{k}}$ be a colorful motif in $G_{{v, w}}$ , then ${v, w, v_{2}, \dots, v_{k}}$ is a colorful motif in G since $v^{⋆}$ is adjacent to some vertex $v_{i}$ in the motif and hence, by construction, $v_{i}$ is adjacent to v or to w and there is an edge between v and w.

The strict composition constructs the disjoint union of the sequence of inputs. Clearly, the disjoint union has a colorful motif if and only if one of the input graphs has a colorful motif. Lemma 2 now yields the result. □

3.4. Component-wise annotated graph problems

In the following, we prove that the following family of problems is diminishable.

Herein, we refer to the set D as the annotated set. The basic idea behind the diminisher for MCA-Π is that we can branch over all possible vertices contained in a solution and add them to the annotated set. That is, we increase the annotated set in favor of decreasing the required solution size. We say that a property Π can be verified in polynomial time, if there is an algorithm that on any input graph $G = (V, E)$ with vertex subset $S \subseteq V$ decides in time polynomial in the size of G whether S fulfills property Π in G.

Lemma 9.
Multi-Component Annotated Π $(k)$ is diminishable if Π can be verified in polynomial time.
Proof.
The main idea of the parameter diminisher is to extend the set D of annotated vertices by each possible vertex in the graph. Formally, given an instance $(G = (V, E), D, k)$ , in polynomial time we either return a trivial Yes- or No-instance equivalent to $(G, D, k)$ or compute an equivalent instance $(G^{}, D^{}, k - 1)$ as follows. For each connected component $G^{'} = (V^{'}, E^{'})$ , check whether $D \cap V^{'}$ fulfills property Π, and if so, return a trivial Yes-instance.

Otherwise, if $D = V$ , then return a trivial No-instance. If $D \neq V$ , then we construct the equivalent instance $(G^{}, D^{}, k - 1)$ . Let $G^{}$ and $D^{}$ be initially empty. For each connected component $G^{'} = (V^{'}, E^{'})$ , consider two cases. If $D \cap V^{'} = V^{'}$ , then add a copy of $G^{'}$ to $G^{}$ . Otherwise, if $D \cap V^{'} ⊊ V^{'}$ , do the following. Let the vertices in $V^{'} ∖ D$ be enumerated as $v_{1}, \dots, v_{ℓ}$ , where $ℓ = | V^{'} ∖ D |$ . For each vertex $i \in [ℓ]$ , add a copy $G_{i}^{'}$ of $G^{'}$ to $G^{}$ . Denote by $D^{i}$ the copy of D in $G_{i}^{'}$ , and by $v_{j}^{i}$ , $j \in [ℓ]$ , the copies of the vertices in $V^{'} ∖ D$ . Add $D^{i} \cup {v_{i}^{i}}$ to $D^{}$ . This finishes the construction. We claim that $(G, D, k)$ is a Yes-instance if and only if $(G^{}, D^{}, k - 1)$ is a Yes-instance.

Let $S \subseteq V^{'}$ be a solution for $(G, D, k)$ , where $G^{'} = (V^{'}, E^{'})$ forms a connected component in G. Let $v_{i} \in S ∖ D$ (note that $S ∖ D \neq \emptyset$ ). Then there is a connected component $G_{i}^{'} = (V_{i}^{'}, E_{i}^{'})$ in $G^{}$ such that $D^{i} \cup {v_{i}^{i}}$ is the set of annotated vertices in $G_{i}^{'}$ . Let $S^{}$ denote the copies of S in $G_{i}^{'}$ . As $G_{i}^{'}$ is isomorphic to $G^{'}$ , $S^{}$ fulfills property Π in $G_{i}^{'}$ . Moreover, $| S^{} ∖ (D^{} \cap V_{i}^{'}) | = | S ∖ ((D \cap V^{'}) \cup {v_{i}}) | = | S ∖ (D \cap V^{'}) | - 1 ⩽ k - 1$ .

Conversely, let $S^{} \subseteq V_{i}^{'}$ be a solution for $(G^{}, D^{}, k - 1)$ , where $G_{i}^{'} = (V_{i}^{'}, E_{i}^{'})$ forms a connected component in G. Let $G^{'} = (V^{'}, E^{'})$ be the connected component in G isomorphic to $G_{i}^{'}$ . Let S be the set of vertices whose copy in $G_{i}^{'}$ is $S^{}$ . Clearly, S fulfills property Π in $G^{'}$ . Note that there is exactly one vertex $v_{i}^{i} \in S^{} \cap D^{}$ such that for its origin $v_{i} \in V^{'}$ holds $v_{i} \notin S \cap D^{}$ . It follows that $| S ∖ (D \cap V^{'}) | = | S^{} ∖ (D^{} \cap V_{i}^{'}) \cup {v_{i}^{i}} | = | S^{} ∖ (D^{} \cap V_{i}^{'}) | + 1 ⩽ k - 1 + 1 = k$ . □

Our first application of Lemma 9 is Π being a defensive alliance* [27], a notion introduced in [39]: Given an undirected graph $G = (V, E)$ , a vertex set S is called a defensive alliance if for all $s \in S$ it holds that $| N_{G} [s] \cap S] ⩾ | N_{G} [s] ∖ S |$ . The problem Defensive Alliance, where, given an undirected graph G and an integer k, the question is whether G contains a defensive alliance of size at most k, is NP-complete and fixed-parameter tractable when parameterized by the solution size k [25,27]. Defensive alliances have the property that if S is a defensive alliance, then each $S^{'} \subseteq S$ forming a maximally connected subgraph is a defensive alliance. Hence, the problem variant MCA-Defensive Alliance is a natural generalization of Defensive Alliance (for the generalization, set $D = \emptyset$ ). Via small modifications, one can prove that MCA-Defensive Alliance remains fixed-parameter tractable when parameterized by the solution size k. As a result, MCA-Defensive Alliance is contained in NP, and hence by Lemma 9 we obtain the following.
Proposition 7.
MCA-Defensive Alliance $(k)$ is diminishable.

Another application of Lemma 9 is Π being a vertex cover. We point out that the classic Vertex Cover problem admits a quadratic kernel when parameterized by the solution size k [8,20]. Note that MCA-Vertex Cover remains trivially NP-complete and contained in FPT when parameterized by the solution size k. However, by Lemma 9 and Theorem 2, its kernelizability changes due to the following. Proposition 8.
MCA-Vertex Cover $(k)$ is diminishable.

3.5. Non-deterministic Turing machine computations

Now we turn our attention to single-tape, single-head, non-deterministic Turing machine computations. A Turing machine is defined as a tuple $M = (Σ, Q, q_{0}, F, δ)$ , where Σ is the alphabet, Q is the set of states, $q_{0} \in Q$ is the initial state, $F \subseteq Q$ are the accepting states, and $δ \subseteq ((Σ \cup {□}) \times Q) \times (Σ \times Q \times {- 1, 0, 1})$ is the transition relation, where □ denotes the blank symbol in an empty cell. The Short NTM Computation problem asks, given a Turing machine M, a word $x \in Σ^{*}$ which is initially written on the tape, and a number k in unary encoding, whether there is a run such that, after k computation steps, the Turing machine M is in an accepting state. This problem is known to be W[1]-hard when parameterized by k and in FPT when parameterized by $(k + | Σ |)$ and when parameterized by $(k + | Q |)$ [20]. In the following we show that the problem does not admit a strict polynomial kernel for these parameterizations unless $P = NP$ .

Proposition 9.
Short NTM Computation $(k + | Σ |)$ is diminishable.

Notice that one can easily find a branching rule that basically simulates the first step, splitting up the various nondeterministic choices. Yet, it is unclear how to construct a strict composition for this problem. While we could easily combine several Turing Machines and then in the first step nondeterministically choose which one we want to use, it is not obvious how we could combine the different input words without increasing the alphabet size. Therefore, we choose a different approach in the following proof.
Proof.
The main idea behind the parameter diminisher for Short NTM Computation $(k + | Σ |)$ is to transform the given Turing machine M to a Turing machine $M^{'} = (Σ, Q^{'}, q_{0}^{'}, F^{'}, δ^{'})$ that computes the last two steps of M, that is step $k - 1$ and step k, in one step. (If $k = 1$ , then the parameter diminisher can produce a trivial Yes- or No-instance.) To do that, we need to encode the letter and its position on the tape that will be read by Turing machine M in step k in the states of Turing machine $M^{'}$ . Additionally, we need to use the states to count the steps in order to allow the Turing machine $M^{'}$ to recognize when it has to compute two steps of M in one step, and we need to encode the position of the tape which the head is currently looking at. Let $x \in Σ^{}$ denote the input string, that is initially written on the tape, starting at cell 0.

Note that in k steps, the head of the Turing machine can potentially only move to and read from cells $- k, - k + 1, \dots, 0, \dots, k - 1, k$ , assuming the initial head position is 0. Hence, we set $\begin{matrix} Q^{'} = {q_{0}^{'}} \cup (Q \times (Σ \cup {□}) \times {- k, \dots, k} \times {- k, \dots, k} \times {1, \dots, k - 1}) \cup {\bar{q}}, \end{matrix}$ where $\bar{q} \notin Q$ . So every state different from $q_{0}^{'}$ and $\bar{q}$ is a tuple consisting of five elements: the state of Turing machine M it corresponds to, the letter that is on a specific position of the tape, that position, the current position of the head, and the current computation step. Each of these states is accepting if the corresponding state of M is accepting, $q_{0}^{'}$ is accepting if $q_{0}$ is accepting, and $\bar{q}$ is not an accepting state.

For every transition in δ from the initial state $q_{0}$ to some state q we create transitions in $δ^{'}$ from the new initial state $q_{0}^{'}$ to all states $(q, x_{i}, i, m, 1)$ such that the following conditions are met.
$- k ⩽ i ⩽ k$ ,

for $1 ⩽ i ⩽ | x |$ , $x_{i}$ is the i-th letter of input x, for $i = 0$ , $x_{0}$ is the letter written by δ into cell 0, and □ otherwise, and

m is the movement of the head in the transition δ, that is, $m \in {- 1, 0, 1}$ .
The following stays unchanged in the transition: the letter that needs to be read by the head for the transition to be possible, the letter written to the tape, and the movement of the head. For every transition from a state q to a state $q^{'}$ in δ, we create transitions from states $(q, x, i, j, t)$ to states $(q^{'}, x^{'}, i, j^{'}, t + 1)$ in $δ^{'}$ , such that the following conditions are met:
$- k ⩽ i ⩽ k$ ,

$x^{'} = x$ , unless $i = j$ , then $x^{'} = y$ , where y is the symbol that Turing machine M writes into cell i according to transition δ,

$j^{'} = j + m$ , where m is the movement of the head in the transition δ, that is, $m \in {- 1, 0, 1}$ , and

$1 ⩽ t ⩽ k - 3$ .
Again, the following stays unchanged in the transition: the letter that needs to be read by the head for the transition to be possible, the letter written to the tape, and the movement of the head. Finally, for every state $(q, x, i, j, k - 2)$ we create a transition in $δ^{'}$ that on reading symbol y goes to state $(q^{'}, x^{'}, i, j^{'}, k - 1)$ without moving the head if the following conditions are met:
There is a transition from q on reading symbol y to a state $q^{⋆}$ in δ with head movement m such that $j + m = i$ , and

there is a transition in δ that, if M is in state $q^{⋆}$ and reads x, goes to state $q^{'}$ .
Otherwise, we create a transition in $δ^{'}$ that goes from state $(q, x, i, j, k - 2)$ and reading symbol y to state $\bar{q}$ without moving the head. No writing is necessary.

Turing machine $M^{'}$ needs to non-deterministically guess the position of the head of Turing machine M in step $k - 1$ and then simulates the behavior of M until step $k - 2$ . If the guess was wrong, then M will make a transition to $\bar{q}$ , a non-accepting state. If the guess was correct, then $M^{'}$ accepts in $k - 1$ steps if and only if M accepts in k steps. □

In Short Binary NTM Computation the input Turing machines are restricted to have a two-element alphabet. Short Binary NTM Computation $(k)$ is in FPT [20] and it is not hard to see that the parameter diminisher for Short NTM Computation $(k + | Σ |)$ is also a parameter diminisher for Short Binary NTM Computation $(k)$ . This yields the following corollary.
Corollary 2.
Short Binary NTM Computation $(k)$ is diminishable.*

We proved a parameter diminisher for Short NTM Computation $(k + | Σ |)$ . Next we present a parameter diminisher for Short NTM Computation parameterized by k and the number of states $| Q |$ combined. Proposition 10.
Short NTM Computation $(k + | Q |)$ is diminishable.
Proof.
The idea behind the parameter diminisher for Short NTM Computation $(k + | Q |)$ is to merge the symbols on the tape at positions $- 1, 0, + 1$ into a single new symbol. In this way we can produce a Turing machine $M^{'}$ that computes the first two steps of the given Turing machine M with a single step. (If $k = 1$ , then the parameter diminisher can produce a trivial Yes- or No-instance.)

More specifically, given a Turing machine $M = (Σ, Q, q_{0}, F, δ)$ , a word $x \in Σ^{}$ , and a positive integer k, we construct a Turing machine $M^{'} = (Σ^{'}, Q, q_{0}, F, δ^{'})$ and a word $x^{'} \in Σ^{' }$ such that $(M^{'}, x^{'}, k - 1)$ is a Yes-instance if and only if $(M, x, k)$ is a Yes-instance. We set $Σ^{'} = Σ \cup ((Σ \cup {□}) \times Σ^{2} \times {- 1, 0, + 1, S})$ . The set ${- 1, 0, + 1, S}$ encodes the position of the head of M when reading a symbol at positions $- 1, 0, + 1$ , while S encodes that this is the first step, and hence that we need to compute two steps of M at once. The new input $x^{'}$ is set to $x^{'} = (□, x_{0}, x_{1}, S) x_{2} \dots x_{n}$ , where $x_{0} \dots x_{n} = x$ .

The transition relation $δ^{'}$ is defined as follows. On symbols in Σ the Turing machine $M^{'}$ behaves like M, while on symbols $(σ_{- 1}, σ_{0}, σ_{+ 1}, i)$ with $i \in {- 1, 0, 1}$ , we simulate the original Turing machine M on the character $σ_{i}$ . If the Turing machine M moves left or right within ${- 1, 0, 1}$ , then we keep the head on the same position and update the value of i. If we move outside the range ${- 1, 0, + 1}$ , then we move the head to the left and right accordingly. Note that when the Turing machine $M^{'}$ returns to this symbol, then the value of i will be automatically correct.

Finally, on symbols $(σ_{- 1}, σ_{0}, σ_{+ 1}, S)$ we are in state $q_{0}$ and simulate the first two steps of the Turing machine M. Also, we replace S according to the movement of the head. This guarantees that $M^{'}$ will only read such a symbol in the very first step and hence computes two steps of M in one step exactly once. It is not difficult to see that $M^{'}$ accepts $x^{'}$ in $k - 1$ steps if and only if M accepts x in k steps. □

4. Problems without semi-strict polynomial kernels

As strict kernels only allow an increase of the parameter value by an additive constant (Definition 1), one may ask whether one can exclude less restrictive versions of strict kernels for parameterized problems using the concept of parameter diminishers. Targeting this question, in this section we study scenarios with a multiplicative (instead of additive) parameter increase by a constant. That is, property (iii) in Definition 1 is replaced by $k^{'} ⩽ c \cdot k$ , for some constant c. We refer to this as semi-strict kernels.

Definition 7 (Semi-Strict Kernel).

A semi-strict kernelization for a parameterized problem L is a polynomial-time algorithm that on input instance $(x, k) \in {0, 1}^{*} \times N$ outputs an instance $(x^{'}, k^{'}) \in {0, 1}^{*} \times N$ , the semi-strict kernel, satisfying:

$(x, k) \in L ⟺ (x^{'}, k^{'}) \in L$ ,

$| x^{'} | ⩽ f (k)$ , for some function f, and

$k^{'} ⩽ c \cdot k$ , for some constant c.

We say that L admits a semi-strict polynomial kernelization if

f (k) \in k^{O (1)}

On the one hand, every strict kernelization with constant c is a semi-strict kernelizations with constant $c + 1$ . On the other hand, if a parameterized problem L admits a semi-strict kernel with constant c, then there is not necessarily a constant $c^{'}$ such that for every input instance $(x, k)$ the obtained parameter value $k^{'}$ of the output instance $(x^{'}, k^{'})$ is upper-bounded by $k^{'} + c^{'}$ . Hence, L does not necessarily admit a strict kernelization. In this sense, Definition 7 generalizes strict kernelizations.

To exclude semi-strict kernels of polynomial size under the assumption $P \neq NP$ , we prove an analogue of Theorem 2 for semi-strict kernelization. To this end, we introduce a stronger version of our parameter diminisher: Formally, we replace property (ii) in Definition 2 by $k^{'} ⩽ k / c$ , for some constant $c > 1$ . We refer to this as strong parameter diminishers.

Definition 8 (Strong Parameter Diminisher).

A strong parameter diminisher for a parameterized problem L is a polynomial-time algorithm that maps instances $(x, k) \in {0, 1}^{*} \times N$ to instances $(x^{'}, k^{'}) \in {0, 1}^{*} \times N$ such that

$(x, k) \in L ⟺ (x^{'}, k^{'}) \in L$ , and

$k^{'} ⩽ k / c$ , for some constant $c > 1$ .

Remark 2.
To simplify arguments in subsequent proofs, we assume without loss of generality that the constant of any strong diminisher is at least two for the remainder of this section. Consider a strong parameter diminisher $D$ with constant $1 < c < 2$ . Let $D^{'}$ be the repetition of $D$ exactly $⌈ {log}_{c} 2 ⌉$ times. Then $D^{'}$ is a strong parameter diminisher with constant $c^{'} : = c^{⌈ {log}_{c} 2 ⌉} ⩾ 2$ .

Next, we show an analogue of Theorem 2 for semi-strict polynomial kernelizations and strong parameter diminishers.
Theorem 3.
Let L be a parameterized problem such that its unparameterized version is NP-hard and ${(x, k) \in L ∣ k ⩽ c} \in P$ , for some constant $c ⩾ 1$ . If L is strongly diminishable and admits a semi-strict polynomial kernel, then $P = NP$ .
Proof.
Let L be a parameterized problem whose unparameterized version is NP-hard and it holds that ${(x, k) \in L ∣ k ⩽ c} \in P$ , for a constant $c ⩾ 1$ . Let $D$ be a strong parameter diminisher for L with constant $c_{d} ⩾ 2$ and let $A$ be a semi-strict polynomial kernelization for L with constant $c_{a} > 1$ . We show that we can solve any instance $(x, k)$ of L, with k being the parameter, in polynomial time. Let $(x, k)$ be an instance of L. Apply $D$ on $(x, k)$ exactly $c_{r} : = ⌈ {log}_{c_{d}} (c_{a} + c_{d}) ⌉$ times to obtain an equivalent instance $D^{c_{r}} (x, k) = (x^{'}, k^{'})$ with $k^{'} ⩽ k / c_{d}^{c_{r}} ⩽ k / (c_{a} + c_{d})$ . Observe that the size of $| (x^{'}, k^{'}) |$ is still polynomial in $| (x, k) |$ as $c_{r}$ is a constant. Next, apply $A$ on $(x^{'}, k^{'})$ to obtain an equivalent instance $(x^{″}, k^{″})$ with $| (x^{″}, k^{″}) | ⩽ k^{' c^{'}}$ , $c^{'} ⩾ 1$ , and $k^{″} ⩽ c_{a} \cdot k^{'} ⩽ c_{a} \cdot k / (c_{a} + c_{d}) < k$ . Repeating the described procedure at most k times produces an instance $(y, k_{y})$ of L with $k_{y} ⩽ c$ , solvable in polynomial time. □

By Theorem 3, if we can give a strong diminisher for a parameterized problem, then it does not admit a semi-strict polynomial kernel, unless $P = NP$ . We next study the Set Cover and the Hitting Set problem. In the Set Cover problem, given a set U called the universe, a family $F \subseteq 2^{U}$ of subsets of U, and an integer k, the question is whether there exists $F^{'} \subseteq F$ with $| F^{'} | ⩽ k$ such that $⋃_{F \in F^{'}} F = U$ . In the Hitting Set problem, given a set U called the universe, a family $F \subseteq 2^{U}$ of subsets of U, and an integer k, the question is whether there exists $U^{'} \subseteq U$ with $| U^{'} | ⩽ k$ such that $F \cap U^{'} \neq \emptyset$ for all $F \in F$ . We show that Set Cover parameterized by $k log n$ , where $n = | U |$ , and Hitting Set parameterized by $k log m$ , where $m = | F |$ , are strongly diminishable and hence, due to Theorem 3, do not admit semi-strict polynomial kernelizations unless $P = NP$ . Note that Hermelin et al. [33] studied these two parameterized problems in the context of lower bounds regarding Turing kernelization.
Theorem 4.
Unless $P = NP$ , Set Cover $(k log n)$ admits no semi-strict polynomial kernel.
Proof.
Let $(U, F = {F_{1}, \dots, F_{m}}, k)$ be an instance of Set Cover $(k log n)$ and assume that $k ⩾ 2$ and $n ⩾ 5$ . If k is odd, then we add a unique element to U, a unique set containing only this element to $F$ , and we set $k : = k + 1$ . Hence, we assume that k is even. The following procedure is a strong parameter diminisher for the problem parameterized by $k log n$ . Let $U^{'} = U$ and for all $F_{i}, F_{j}$ create $F_{{i, j}}^{'} = F_{i} \cup F_{j}$ . Let $F^{'} = {F_{{i, j}}^{'} | i \neq j}$ and set $k^{'} = k / 2$ . This yields in polynomial time the instance $(U^{'}, F^{'}, k^{'})$ of Set Cover $(k log n)$ . In the following we show that $(U, F, k)$ is a Yes-instance if and only if $(U^{'}, F^{'}, k^{'})$ is a Yes-instance. Furthermore, we argue that $k^{'} log n^{'} < (k log n) / c$ for some constant $c > 1$ , where $n^{'} = | U^{'} |$ .

(⇒) Assume that there is a set cover $C \subseteq F$ for U of size k. Let $C = {C_{1}, C_{2}, \dots, C_{k}}$ and let $C^{'} = {C_{1} \cup C_{2}, C_{3} \cup C_{4}, \dots, C_{k - 1} \cup C_{k}}$ . Then clearly $C^{'} \subseteq F^{'}$ is a set cover for $U^{'}$ of size $k / 2$ .

(⇐) Assume that there is a set cover $C^{'}$ for $U^{'}$ of size $k / 2$ . Let $C^{'} = {C_{1}^{'}, C_{2}^{'}, \dots, C_{k / 2}^{'}}$ , let $C_{i}^{'} = C_{i} \cup C_{i^{'}}$ and let $C = {C_{1}, C_{1^{'}}, C_{2}, C_{2^{'}}, \dots, C_{k / 2}, C_{k / 2^{'}}}$ . Then clearly $C \subseteq F$ is a set cover for U of size at most k. Furthermore, we have that $m^{'} = (\binom{m}{2})$ . It follows that $\begin{matrix} k^{'} log n^{'} ⩽ \frac{k + 1}{2} log (n + 1) \overset{k ⩾ 2}{⩽} \frac{3 k}{4} log (n + 1) ⩽ \frac{\sqrt{3}}{2} k log ({(n + 1)}^{\sqrt{3} / 2}) \overset{n ⩾ 5}{⩽} \frac{\sqrt{3}}{2} k log (n) . \end{matrix}$ Note that in the first inequality, we consider the cases in which the instance was modified such that k is even. It follows that for $k > 2$ the parameter decreases by at least a factor of $\sqrt{3} / 2$ and for $k = 2$ the parameter diminisher produces either a trivial Yes- or a trivial No-instance (each with a constant number of vertices). □

A strong parameter diminisher for Hitting Set $(k log m)$ can be constructed in a similar fashion.
Theorem 5.
Unless $P = NP$ , Hitting Set $(k log m)$ admits no semi-strict polynomial kernel.
Proof.
Let $(U = {u_{1}, \dots, u_{n}}, F, k)$ be an instance of Hitting Set $(k log m)$ and assume that $k ⩾ 2$ and $m = | F | ⩾ 5$ . If k is odd, then we add a unique element u to U, a unique set F containing only this element to $F$ , and we set $k : = k + 1$ . Construct the universe $U^{'} = {u_{i, j} ∣ u_{i}, u_{j} \in U, i < j}$ . Construct the set $F^{'}$ of subsets of $U^{'}$ as follows: For each $F \in F$ , add the set $F^{'} = {u_{i, j} ∣ u_{i} \in F \lor u_{j} \in F, 1 ⩽ i < j ⩽ n}$ to $F^{'}$ . Set $k^{'} = k / 2$ . This finishes the construction. Note that $\begin{array}{l} k^{'} log m^{'} & ⩽ \frac{k + 1}{2} log (m + 1) \overset{k ⩾ 2}{⩽} \frac{3 k}{4} log (m + 1) ⩽ \frac{\sqrt{3}}{2} k log ({(m + 1)}^{\sqrt{3} / 2}) \overset{m ⩾ 5}{⩽} \frac{\sqrt{3}}{2} k log (m) . \end{array}$ We show that $(U, F, k)$ is a Yes-instance if and only if $(U^{'}, F^{'}, k^{'})$ is a Yes-instance.

(⇒) Assume that there is a hitting set $H = {u_{i_{1}}, u_{i_{2}}, \dots, u_{i_{k}}} \subseteq U$ of size k, where $i_{j} \in [n]$ for all $j \in [k]$ and $i_{1} < i_{2} < \dots < i_{k}$ . Let $H^{'} = {u_{i_{1}, i_{2}}, u_{i_{3}, i_{4}}, \dots, u_{i_{k - 1}, i_{k}}}$ . We claim that $H^{'} \cap F^{'} \neq \emptyset$ for all $F^{'} \in F^{'}$ . Let $F^{'}$ be obtained by F. Since H is a hitting set, we know that there is a $j \in [k]$ such that $u_{i_{j}} \in H \cap F$ . Hence, $F^{'}$ contains the elements $u_{i_{j - 1}, i_{j}}$ (if $j > 1$ ) and $u_{i_{j}, i_{j + 1}}$ (if $j < k$ ). Since one of them is contained in $H^{'}$ , it holds true that $H^{'} \cap F^{'} \neq \emptyset$ .

(⇐) Assume that there is a hitting set $H^{'} \subseteq U^{'}$ of size $k^{'}$ . Let $H^{'} = {u_{i, j} ∣ i, j \in [n], i < j}$ . We claim that $H = {u_{ℓ} ∣ \exists i : u_{i, ℓ} \in H^{'} \lor u_{ℓ, i} \in H^{'}}$ is a hitting set of $F$ . Let F be an arbitrary set, and let $F^{'}$ denote the set in $F^{'}$ obtained from F. Since $H^{'}$ is a hitting set, we know that there are $i, j \in [n]$ , $i < j$ such that $u_{i, j} \in H^{'} \cap F^{'}$ . By construction, either $u_{i} \in F$ or $u_{j} \in F$ . Hence, $H \cap F \neq \emptyset$ . □

Seeking for parameter diminishers to exclude strict polynomial kernelizations raises the question whether there are parameterized problems that are not (strongly) diminishable. In the following, we prove that under the Exponential Time Hypothesis, or ETH for short [35], there are natural problems that do not admit strong parameter diminishers. Here we restrict ourselves to problems where we have a parameter diminisher. The Exponential Time Hypothesis states that there is no algorithm for 3-CNF-Sat running in $2^{o (n)} poly (n + m)$ time, where n and m denote the number of variables and clauses, respectively.
Theorem 6.
Assuming ETH, none of the following is strongly diminishable: CNF-Sat $(n)$ , Rooted Path $(k)$ , Clique $(Δ)$ , Clique $(tw)$ , and Clique $(bw)$ .

The following lemma is the key tool for excluding strong parameter diminishers under ETH. Roughly, it can be understood as saying that a strong parameter diminisher can improve the running time of existing algorithms.
Lemma 10.
Let L be a parameterized problem. If there is an algorithm that solves any instance $(x, k) \in L$ in $2^{O (k)} \cdot | x |^{O (1)}$ time and L is strongly diminishable, then there is an algorithm that solves L in $2^{O (k / f (x, k))} \cdot | x |^{f {(x, k)}^{O (1)}} + T_{f} (x, k)$ time, where $f : L \to N$ is a $T_{f}$ -time-computable function mapping instances $(x, k)$ of L to the natural numbers with the following property: For every constant c there is a natural number n such that for all instances $(x, k) \in L$ we have that $| x | ⩾ n$ implies that $f (x, k) ⩾ c$ .
Proof.
Let L be a parameterized problem. Let $A$ be an algorithm that solves any instance $(x, k) \in L$ in $2^{c_{1} \cdot k} \cdot | x |^{c_{2}}$ time with constants $c_{1}, c_{2} > 0$ and let $D$ be a strong parameter diminisher for L with constant $d ⩾ 2$ . Recall that by definition of a strong parameter diminisher, the size of the instance grows at most polynomially each time $D$ is applied. Let $b ⩾ 1$ be a constant such that the size of the instance obtained by applying $D$ once to $(x, k)$ is upper-bounded by $| x |^{b}$ . We set $c : = min {2, b}$ . Let $f : L \to N$ be a $T_{f}$ -time-computable function such that $f (x, k) ⩾ c$ for all $(x, k) \in L$ with $| x | ⩾ c_{0}$ for some constant $c_{0} \in N$ .

Let $(x^{'}, k^{'})$ be the instance of L obtained by applying $D ⌈ {log}_{c} f (x, k) ⌉$ times, where $f (x, k)$ is computed in $T_{f} (x, k)$ time, to instance $(x, k) \in L$ with $| x | ⩾ c_{0}$ . We obtain $\begin{matrix} | x^{'} | ⩽ | x |^{b^{⌈ {log}_{c} f (x, k) ⌉}} ⩽ | x |^{b^{2 {log}_{c} f (x, k)}} ⩽ | x |^{f {(x, k)}^{c_{3}}}, for some constant c_{3} ⩾ 1 . \end{matrix}$ Furthermore, the parameter decreases by the constant factor d each time the diminisher is applied, hence $\begin{matrix} k^{'} = k / d^{⌈ {log}_{c} f (x, k) ⌉} ⩽ k / d^{{log}_{c} f (x, k)} ⩽ k / d^{{log}_{d} f (x, k)} ⩽ k / f (x, k) . \end{matrix}$ Finally, applying $A$ on $(x^{'}, k^{'})$ solves $(x^{'}, k^{'})$ in time $\begin{matrix} 2^{c_{1} \cdot k^{'}} \cdot {| x^{'} |}^{c_{2}} ⩽ 2^{c_{1} \cdot k / f (x, k)} \cdot | x |^{c_{2} \cdot f {(x, k)}^{c_{3}}} \in 2^{O (k / f (x, k))} \cdot | x |^{f {(x, k)}^{O (1)}} . \end{matrix}$ □

We apply Lemma 10 to exclude the existence of strong parameter diminishers under ETH as follows. Consider a problem where we know a running time lower bound based on the ETH and we also know an algorithm that matches this lower bound. Then, due to Lemma 10, for many problems a strong parameter diminisher and a suitable choice for the function f would imply the existence of an algorithm whose running time breaks the lower bound.

Chen et al. [13] showed that CNF-Sat $(n)$ and Rooted Path $(k)$ are diminishable. We show that we cannot obtain strong diminishability for these problems unless the ETH breaks. Recall CNF-Sat $(n)$ , the parameterized problem of deciding whether a given Boolean formula with n variables in conjunctive normal form is satisfiable.
Proposition 11.
Assuming ETH, CNF-Sat $(n)$ is not strongly diminishable.
Proof.
CNF-Sat can be solved in $O^{} (2^{n})$ time via a brute-force algorithm $A$ , but does not admit a $2^{o (n)}$ time algorithm under the ETH. By Lemma 10 with algorithm $A$ and $f (ϕ) = log n$ , CNF-Sat $(n)$ does not admit a strong parameter diminisher unless the ETH breaks. □
Proposition 12.
Assuming* ETH, Rooted Path $(k)$ is not strongly diminishable.
Proof.
Hamiltonian Path on an n-vertex graph reduces trivially to Rooted Path by adding a universal vertex and taking it as the root and setting the length of the path $k = n$ . As Hamiltonian Path does not admit a $2^{o (n)}$ time algorithm unless the ETH breaks [42], Rooted Path does not admit a $2^{o (n)}$ time algorithm unless the ETH breaks. There is an algorithm for Rooted Path $(k)$ running in $2^{O (k)} poly (n)$ time [2]. Let $(G = (V, E), k)$ be an instance of Rooted Path $(k)$ and set $f (G, k) = log (| V |) = log n$ . By Lemma 10 we get an algorithm for Rooted Path $(k)$ running in $2^{O (k / log n)} \cdot | G |^{{(log n)}^{O (1)}} \in 2^{o (n)}$ time. Hence, Rooted Path $(k)$ does not admit a strong parameter diminisher unless the ETH breaks. □

Next, we show that for most parameterizations we considered, Clique does not admit a strong parameter diminisher unless the ETH breaks.
Proposition 13.
Assuming ETH, Clique $(bw)$ , Clique $(Δ)$ , and Clique $(tw)$ are not strongly diminishable.
Proof.
Let $p \in {bw, Δ, tw}$ . Clique can be solved in $O^{*} (2^{p})$ time via a dynamic programming (brute-force) algorithm $A$ , but does not admit a $2^{o (n)}$ time algorithm under ETH [42]. Note that $p \in O (n)$ . By Lemma 10 with algorithm $A$ and $f (G, k) = log (| V |) = log n$ , Clique $(p)$ does not admit a strong parameter diminisher unless the ETH breaks. □

Note that we do not obtain this result for Clique $(cw)$ , since $cw (G) \in O (n^{2})$ , where n is the number of vertices of G.

Finally, note that it is not hard to observe that if we can exclude a strong parameter diminisher for a problem L parameterized by k under ETH, then we can exclude a parameter diminisher for L parameterized by $log k$ under ETH. Thus, it would be interesting to know whether there is a way to exclude the existence of parameter diminishers avoiding this exponential gap between the parameterizations.
5. Conclusion

We showed that for several natural problems a strict polynomial-size problem kernel is as likely as $P = NP$ . Since basically all observed (natural and practically relevant) polynomial kernels are strict, this reveals that the existence of valuable kernels may be tighter connected to the P vs. NP problem than previously expected (in almost all previous work a connection is drawn to a collapse of the polynomial hierarchy to its third level, and the conceptual framework used there is more technical than the one used here). Our work is based on results of Chen, Flum, and Müller [13] and shows that their basic ideas can be extended to a larger class of problems than dealt with in their work.

The diminisher framework leaves several challenges for future work. Are there natural problems where the presented framework is able to refute strict polynomial kernels while the composition framework [7] is not? It is not clear whether a framework based on a weaker assumption is even able to produce results that a framework based on a stronger assumption is not able to produce. This possibly also ties in with the question whether there are “natural” parameterized problems that admit a polynomial kernel but no strict polynomial kernel.5

⁵

Note that Chen, Flum, and Müller [13, Proposition 3.3] presented an artificial parameterized problem admitting a polynomial kernel but no strict polynomial kernel.

We close with several concrete open problems:

We proved that Multicolored Path $(k)$ is diminishable (and thus refutes a strict polynomial kernel unless $P = NP$ ). Can this result be extended to the uncolored version of the problem? This is also open for the directed case.

Are Connected Vertex Cover $(k)$ or Hitting Set $(n)$ diminishable?

Is Internal Steiner Tree $(k + | T |)$ [34] diminishable?

Clique $(Δ)$ , Clique $(tw)$ , Clique $(bw)$ do not have strong diminishers under the ETH (Section 4). Is this also true for Clique $(cw)$ ?

Footnotes

Acknowledgements

This work was initiated during the research retreat of the Theoretical Computer Science group of the Universität of Tübingen in Sulz (Neckar), September 2016. An extended abstract of this paper appears in the proceedings of the 14th Conference on Computability in Europe (CiE 2018) []. We are grateful to two anonymous reviewers of Computability for their constructive feedback that helped improving the presentation.

TF acknowledges support by the DFG, project DAMM (NI 369/13) and project TORE (NI 369/18). DH acknowledges support by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement number 631163.11, and by the ISRAEL SCIENCE FOUNDATION (grant No. 551145/14), and also support by a DFG Mercator fellowship, project DAMM (NI 369/13) while staying at TU Berlin (August–September 2016). AK acknowledges support by the DFG Emmy Noether program (KR 4042/2). HM acknowledges support by the DFG, projects DAPA (NI 369/12) and MATE (NI 369/17).

Problem zoo

References

F.N.

Abu-Khzam and

Fernau, Kernels: Annotated, proper and induced, in: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), LNCS, Vol. 4169, Springer, 2006, pp. 264–275. doi:10.1007/11847250_24.

Alon,

Yuster and

Zwick, Color-coding, J ACM 42(4) (1995), 844–856.

Betzler,

Guo,

Komusiewicz and

Niedermeier, Average parameterization and partial kernelization for computing medians, J. Comput. Syst. Sci. 77(4) (2011), 774–789. doi:10.1016/j.jcss.2010.07.005.

Betzler,

van Bevern,

M.R.

Fellows,

Komusiewicz and

Niedermeier, Parameterized algorithmics for finding connected motifs in biological networks, IEEE/ACM Trans. Comput. Biology Bioinform. 8(5) (2011), 1296–1308. doi:10.1109/TCBB.2011.19.

Biniaz,

Maheshwari and

M.H.M.

Smid, On the hardness of full Steiner tree problems, J. Discrete Algorithms 34 (2015), 118–127. doi:10.1016/j.jda.2015.05.013.

Binkele-Raible,

Fernau,

F.V.

Fomin,

Lokshtanov,

Saurabh and

Villanger, Kernel(s) for problems with no kernel: On out-trees with many leaves, ACM Trans. Algorithms 8(4) (2012), 38. doi:10.1145/2344422.2344428.

H.L.

Bodlaender,

R.G.

Downey,

M.R.

Fellows and

Hermelin, On problems without polynomial kernels, J. Comput. Syst. Sci. 75(8) (2009), 423–434. doi:10.1016/j.jcss.2009.04.001.

J.F.

Buss and

Goldsmith, Nondeterminism within P, SIAM J. Comput. 22(3) (1993), 560–572. doi:10.1137/0222038.

Cai,

Chen,

R.G.

Downey and

M.R.

Fellows, Advice classes of parameterized tractability, Ann. Pure Appl. Logic 84(1) (1997), 119–138. doi:10.1016/S0168-0072(95)00020-8.

10.

Chen,

Fernau,

I.A.

Kanj and

Xia, Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, SIAM J. Comput. 37(4) (2007), 1077–1106. doi:10.1137/050646354.

11.

Chen,

I.A.

Kanj and

Jia, Vertex cover: Further observations and further improvements, J. Algorithms 41(2) (2001), 280–301. doi:10.1006/jagm.2001.1186.

12.

Chen,

Flum and

Müller, Lower bounds for kernelizations and other preprocessing procedures, in: Proceedings of the 5th Conference on Computability in Europe (CiE 2009), Lecture Notes in Computer Science, Vol. 5635, Springer, 2009, pp. 118–128.

13.

Chen,

Flum and

Müller, Lower bounds for kernelizations and other preprocessing procedures, Theory Comput. Syst. 48(4) (2011), 803–839. doi:10.1007/s00224-010-9270-y.

14.

Chvátalová,

Dewdney,

Gibbs and

Korfhage, The bandwidth problem for graphs – a collection of recent results, Technical Report, CS 7502, Department of Computer Science, Southern Methodist University, 1975.

15.

Cygan,

F.V.

Fomin,

Ł.

Kowalik,

Lokshtanov,

Marx,

Pilipczuk,

Pilipczuk and

Saurabh, Parameterized Algorithms, Springer, 2015.

16.

Cygan,

Pilipczuk and

Pilipczuk, Known algorithms for edge clique cover are probably optimal, SIAM J. Comput. 45(1) (2016), 67–83. doi:10.1137/130947076.

17.

Cygan,

Pilipczuk,

Pilipczuk and

J.O.

Wojtaszczyk, Kernelization hardness of connectivity problems in d-degenerate graphs, Discrete Appl. Math. 160(15) (2012), 2131–2141. doi:10.1016/j.dam.2012.05.016.

18.

Díaz,

Petit and

M.J.

Serna, A survey of graph layout problems, ACM Comput. Surv. 34(3) (2002), 313–356. doi:10.1145/568522.568523.

19.

Diestel, Graph Theory, 4th edn, Springer, 2010.

20.

R.G.

Downey and

M.R.

Fellows, Parameterized Complexity, Monographs in Computer Science, Springer, 1999.

21.

R.G.

Downey and

M.R.

Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.

22.

R.G.

Downey,

M.R.

Fellows and

Stege, Parameterized complexity: A framework for systematically confronting computational intractability, in: Proceedings of a DIMACS Workshop on Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 49, DIMACS/AMS, 1997, pp. 49–99.

23.

S.E.

Dreyfus and

R.A.

Wagner, The Steiner problem in graphs, Networks 1(3) (1971), 195–207. doi:10.1002/net.3230010302.

24.

M.R.

Fellows,

Kulik,

F.A.

Rosamond and

Shachnai, Parameterized approximation via fidelity preserving transformations, J. Comput. Syst. Sci. 93 (2018), 30–40. doi:10.1016/j.jcss.2017.11.001.

25.

Fernau, Extremal kernelization: A commemorative paper, in: Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), Lecture Notes in Computer Science, Vol. 10765, Springer, 2017, pp. 24–36. doi:10.1007/978-3-319-78825-8_3.

26.

Fernau,

Fluschnik,

Hermelin,

Krebs,

Molter and

Niedermeier, Diminishable parameterized problems and strict polynomial kernelization, in: Proceedings of the 14th Conference on Computability in Europe (CiE 2018), Lecture Notes in Computer Science, Vol. 10936, Springer, 2018, pp. 161–171.

27.

Fernau and

Raible, Alliances in graphs: A complexity-theoretic study, in: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), Vol. II, Institute of Computer Science AS CR, Prague, 2007, pp. 61–70.

28.

Flum and

Grohe, Parameterized Complexity Theory, Springer, 2006.

29.

Fluschnik,

G.B.

Mertzios and

Nichterlein, Kernelization lower bounds for finding constant-size subgraphs, in: Proceedings of the 14th Conference on Computability in Europe (CiE 2018), Lecture Notes in Computer Science, Vol. 10936, Springer, 2018, pp. 183–193.

30.

Fortnow and

Santhanam, Infeasibility of instance compression and succinct PCPs for NP, J. Comput. Syst. Sci. 77(1) (2011), 91–106. doi:10.1016/j.jcss.2010.06.007.

31.

A.C.

Giannopoulou,

G.B.

Mertzios and

Niedermeier, Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs, Theor. Comput. Sci. 689 (2017), 67–95. doi:10.1016/j.tcs.2017.05.017.

32.

Guo and

Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT News 38(1) (2007), 31–45. doi:10.1145/1233481.1233493.

33.

Hermelin,

Kratsch,

Soltys,

Wahlström and

Wu, A Completeness Theory for Polynomial (Turing) Kernelization, Algorithmica 71(3) (2015), 702–730.

34.

Huang,

Lee,

Gao and

Hsieh, The internal Steiner tree problem: Hardness and approximations, J. Complexity 29(1) (2013), 27–43. doi:10.1016/j.jco.2012.08.005.

35.

Impagliazzo and

Paturi, On the complexity of k-SAT, J. Comput. Syst. Sci. 62(2) (2001), 367–375. doi:10.1006/jcss.2000.1727.

36.

R.M.

Karp and

Lipton, Turing machines that take advice, L’Enseignement Mathématique 28(2) (1982), 191–209.

37.

N.G.

Kinnersley, The vertex separation number of a graph equals its path-width, Inf. Process. Lett. 42(6) (1992), 345–350. doi:10.1016/0020-0190(92)90234-M.

38.

Kratsch, Recent developments in kernelization: A survey, Bulletin of the EATCS 113 (2014).

39.

Kristiansen,

S.M.

Hedetniemi and

S.T.

Hedetniemi, Alliances in graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 48 (2004), 157–177.

40.

Lin and

Xue, On the terminal Steiner tree problem, Inf. Process. Lett. 84(2) (2002), 103–107. doi:10.1016/S0020-0190(02)00227-2.

41.

Lin,

Feng,

Chen and

Li, Partition on trees with supply and demand: Kernelization and algorithms, Theor. Comput. Sci. 657 (2017), 11–19. doi:10.1016/j.tcs.2016.06.044.

42.

Lokshtanov,

Marx and

Saurabh, Lower bounds based on the Exponential Time Hypothesis, Bulletin of the EATCS (2011), 41–72.

43.

Lokshtanov,

Panolan,

M.S.

Ramanujan and

Saurabh, Lossy kernelization, in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, 2017, pp. 224–237. doi:10.1145/3055399.3055456.

44.

Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

45.

Schäfer,

Komusiewicz,

Moser and

Niedermeier, Parameterized computational complexity of finding small-diameter subgraphs, Optimization Letters 6(5) (2012), 883–891. doi:10.1007/s11590-011-0311-5.

46.

Sorge and

Weller, The graph parameter hierarchy, 2018, https://manyu.pro/assets/parameter-hierarchy.pdf.

47.

Xiao and

Kou, Kernelization and parameterized algorithms for 3-path vertex cover, in: Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation (TAMC 2017), LNCS, Vol. 10185, Springer, 2017, pp. 654–668. doi:10.1007/978-3-319-55911-7_47.

Diminishable parameterized problems and strict polynomial kernelization

Abstract

Keywords

1. Introduction

1 We note that this was the first definition of kernelization [20,22] and can still be found as an alternative definition for kernelization in the literature (e.g., [41,47]).

2 Edge Clique Cover is the problem of, given an undirected graph G and an integer k, deciding whether all edges of G can be covered by k subgraphs of G each forming a clique.

Definition 2 (Parameter Diminisher).

Theorem 2 ([13]).

Definition 3 (Parameter-Constant-Increasing Reduction).

Definition 5 (Strict Composition).

3.1. Clique and biclique

Definition 7 (Semi-Strict Kernel).

Definition 8 (Strong Parameter Diminisher).

Footnotes

Acknowledgements

Problem zoo

References

¹
We note that this was the first definition of kernelization [20,22] and can still be found as an alternative definition for kernelization in the literature (e.g., [41,47]).

²
Edge Clique Cover is the problem of, given an undirected graph G and an integer k, deciding whether all edges of G can be covered by k subgraphs of G each forming a clique.