How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?

Abstract

In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarský et al. (J Comput Syst Sci 84:219–242, 2017) proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a c-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most c, where $c \ge 1$ is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer $c \ge 1$, and that Dominating Set does not for any integer $c \ge 2$ even on degenerate graphs, unless $\text {NP} \subseteq \text {coNP}/\text {poly}$. For the positive result, we build on the techniques of Jansen and Bodlaender (Proceedings of the 28th symposium on theoretical aspects of computer science (STACS), volume 9 of LIPIcs, pp 177–188, 2011), and for the negative result we use a polynomial parameter transformation for $c\ge 3$ and an or-cross-composition for $c = 2$. As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for $c = 1$, our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter.

1 Introduction

Motivation There is a whole area of parameterized algorithms and kernelization investigating the complexity ecology (see for example [28]), where the objective is to consider a structural parameter measuring how “complex” is the input, rather than the size of the solution. For instance, parameterizing a problem by the treewidth of its input graph has been a great success for FPT algorithms, triggered by Courcelle’s theorem [6] stating that any problem expressible in MSO logic is FPT parameterized by treewidth. However, the situation is not as good for kernelization, as many problems do not admit polynomial kernels when parameterized by treewidth unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [2].

Of fundamental importance within structural parameters are parameters measuring the so-called “distance from triviality” of the input graphs, like the size of a vertex cover (distance to an independent set) or of a feedback vertex set (distance to a forest). Unlike treewidth, these parameters may lead to both positive and negative results for polynomial kernelization. An elegant way to generalize these parameters is to consider a parameter allowing to quantify the triviality of the resulting instance, measured in terms of its treewidth. More precisely, for a positive integer c, a c-treewidth modulator of a graph G is a set of vertices X such that the treewidth of $G-X$ is at most c. Note that for $c=0$ (resp. $c=1$), a c-treewidth modulator corresponds to a vertex cover (resp. feedback vertex set).

Treewidth modulators have been extensively studied in kernelization, especially on classes of sparse graphs, where they have been at the heart of the recent developments of meta-theorems for obtaining linear and polynomial kernels on graphs on surfaces [3], minor-free graphs [16], and topological-minor-free graphs [20, 23], all based in a generic technique known as protrusion replacement. However, as observed in [18, 23], if one tries to move further in the families of sparse graphs by considering, for instance, graphs of bounded expansion, for several natural problems such as Treewidth-t Vertex Deletion (minimizing the number of vertices to be removed to get a graph of treewidth at most t), parameterizing by a treewidth modulator is as hard as on general graphs.

This observation led Gajarský et al. [18] to consider another type of modulators, namely c-treedepth modulators (defined analogously to c-treewidth modulators), where treedepth is a graph invariant—which we define in Sect. 2 – that plays a crucial structural role on graphs of bounded expansion and nowhere dense graphs [26]. Gajarský et al. [18] proved that any graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs when parameterized by the size of a c-treedepth modulator. Shortly afterwards this result was obtained, the authors asked [29] to investigate this parameter on general graphs, namely to find natural problems that admit and that do not admit polynomial kernels parameterized by the size of a c-treedepth modulator. More precisely, are there natural problems $\varPi _1$ and $\varPi _2$ fitting into the framework of [18] such that $\varPi _1/c$-tdmod admits a polynomial kernel on general graphs, but $\varPi _2/c$-tdmod does not?¹

Our results In this article we answer the above question by proving that Vertex Cover and Dominating Set are such problems $\varPi _1$ and $\varPi _2$, respectively. Let us now elaborate a bit more on our results, the techniques we use to prove them, and how do they compare to previous work in the area (see the preliminaries of Sect. 2 for any undefined terminology).

Note first that both VC/c-tdmod and DS/c-tdmod (where DS stands for Dominating Set) are FPT on general graphs, as they are FPT by treewidth [6], which is a smaller parameter than c-tdmod, as for any graph G and any integer $c \ge 0$, it holds that $\mathsf{tw}(G) \le \mathsf{td}(G) - 1 \le$ c-$\mathsf{tdmod} (G) + c -1$. Thus, asking for polynomial kernels is a pertinent question.

In Sect. 3 we prove that VC/c-tdmod admits a polynomial kernel on general graphs. Our approach is based on the techniques introduced by Jansen and Bodlaender [21] to prove that VC/1-twmod (or equivalently, IS/FVS) admits a polynomial kernel. As in [21], we in fact provide a polynomial kernel for IS/c-tdmod, which is easily seen to be equivalent to VC/c-tdmod. More precisely, we use three reduction rules inspired from the rules given in [21], and we present a recursive algorithm that, starting from a c-treedepth modulator, constructs an appropriate $(c-1)$-treedepth modulator and calls itself inductively. The kernel obtained in this manner has $x^{2^{\mathcal {O}(c^2)}}$ vertices, where x is the size of the c-treedepth modulator. This result completes the following panorama of structural parameterization for Vertex Cover, which has been a real testbed for structural parameterizations in the last years:

• VC/1-twmod (or equivalently, VC/FVS) admits a polynomial kernel [21].

• VC/c-twmod for $c \ge 2$ does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [8].

• VC/2-degmod (distance to a graph of maximum degree 2) and VC/c-CVD (distance to a disjoint collection of cliques of size at most c) admit a polynomial kernel [25]. Note that our result generalizes the latter kernel, as a disjoint collection of cliques of size at most c is a particular case of a graph having treedepth at most c.

• VC/pfm (distance to a pseudoforest) admits a polynomial kernel [17].

In Sect. 4 we turn to negative results for Dominating Set. We provide a characterization, according to the value of c, of the existence of polynomial kernels for DS/c-tdmod on degenerate graphs. Indeed, using the results of Philip et al. [30] it is almost immediate to prove that DS/1-tdmod (or equivalently, DS/VC) admits a polynomial kernel on degenerate graphs. For $c \ge 3$, we rule out the existence of polynomial kernels for DS/c-tdmod on 2-degenerate graphs by a simple polynomial parameter transformation from DS/1-tdmod on general graphs, which does not admit polynomial kernels unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [11]. The remaining case, namely DS/2-tdmod, turns out to be more interesting, and we rule out the existence of polynomial kernels on 4-degenerate graphs by providing an or-cross-composition from 3-Sat. This dichotomy for the existence of polynomial kernels for DS/c-tdmod on degenerate graphs is to be compared with the dichotomy for VC/c-twmod on general graphs discussed above [8, 21].

As mentioned before, it is commonly admitted that almost no natural problem admits a polynomial kernel parameterized by $\mathsf{tw}$, or even with $\mathsf{td}$. However, to the best of our knowledge the only published negative results are those in [2], where the authors prove that IS/tw and DS/tw do not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$. As this result only holds for general graphs, for the sake of completeness we complete it in Sect. 5, by showing that a large majority of the problems considered in [18] having an almost linear kernel parameterized by c-tdmod on nowhere dense graphs do not admit polynomial kernels parameterized by $\mathsf{td}$, even on planar graphs of bounded maximum degree.

2 Preliminaries

Graphs Unless explicitly mentioned, all graphs considered here are simple and undirected, and we refer the reader to [10] for any undefined notation. Given a graph $G=(V,E)$ and $X \subseteq V$, we denote $N_X(v) = N(v) \cap X$, where $N(v) = \{u \in V \mid \{u,v\} \in E\}$. We denote by $\alpha (G)$ the size of a maximum independent set of G. For any function f defined on any induced subgraph of a given graph G, given a subset of vertices $V'$ of G, we denote $f(V')=f(G[V'])$ (for example, $\alpha (V') = \alpha (G[V'])$). For any integer n, we denote $[n]=\{i \in \mathbb {N}, 1 \le i \le n\}$.

For the following definitions related to treedepth, bounded expansion, and nowhere dense graph classes, we refer the reader to [26] for more details, and we only recall here some basic notations and facts. The treedepth of a graph G (denoted $\mathsf{td}(G)$) is the minimum height of a rooted forest F (called a treedepth decomposition) such that G is a subgraph of the closure of F, where the closure of a rooted tree is the graph obtained by adding an edge between any vertex and all its ancestors, and the height of a rooted tree is the number of vertices in a longest path from the root to a leaf. Let $c \ge 1$ be an integer. A c-treedepth modulator is a subset of vertices $X \subseteq V$ such that $\mathsf{td}(G[V{\setminus } X]) \le c$, and we denote by c-$\mathsf{tdmod} (G)$ the size of a smallest c-treedepth modulator of G. A c-treewidth modulator is defined in the same way. Recall that as these parameters are greater than their associated measure (i.e., $\mathsf{tw}(G) \le c$-$\mathsf{twmod} (G)+c$ and $\mathsf{tw}(G) \le \mathsf{td}(G) \le c$-$\mathsf{tdmod} (G)+c$, where $\mathsf{tw}(G)$ denotes the treewidth of G) the negative results for kernelization by treewidth and treedepth do not immediately apply, but the positive FPT results do.

Concerning graph classes, we recall that in the sparse graph hierarchy, graphs of bounded expansion (BE) and nowhere dense graphs (ND) are related to classic sparse families as follows (see [26] for the definitions): planar graphs $\subseteq$ minor-free graphs $\subseteq$ BE $\subseteq$ ND. Note also that the class of graphs of bounded degeneracy is a natural superclass of BE (intuitively, BE also requires the shallow minors to be degenerate), and is incomparable with ND.

We refer the reader to Appendix A for the definition and acronyms of problems considered in the paper, like IS for the independent set problem.

Parameterized complexity We refer the reader to [7, 13, 15, 27] for more details on parameterized complexity and kernelization, and we recall here only some basic definitions, with special emphasis on tools for polynomial kernelization. A parameterized problem is a language $L \subseteq \varSigma ^* \times \mathbb {N}$, for some finite alphabet $\varSigma$. For an instance $I=(x,k) \in \varSigma ^* \times \mathbb {N}$, k is called the parameter. Given a classical (non-parameterized) decision problem $L_{c} \subseteq \varSigma ^*$ and a function $\kappa : \varSigma ^* \rightarrow \mathbb {N}$, we denote by $L_{c}/\kappa = \{(x,\kappa (x)\} \mid x \in L_{c}\}$ the associated parameterized problem. For example, IS/c-tdmod denotes the independent Set problem parameterized by the size of a c-treedepth modulator.

A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm A, a computable function f, and a constant c such that given an instance $I=(x,k)$, A (called an FPT algorithm) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$. Given a computable function g, a kernelization algorithm (or simply a kernel) for a parameterized problem L of sizeg is an algorithm A that given any instance $I=(x,k)$ of L, runs in polynomial time and returns an equivalent instance $I'=(x',k')$ (i.e., $I'\in L$ if and only if $I\in L$) with $|I'|+k' \le g(k)$. It is well-known that the existence of an FPT algorithm is equivalent to the existence of a kernel (whose size may be exponential or larger), implying that problems admitting a polynomial kernel form a natural subclass of FPT.

Some tools for (ruling out) polynomial kernelization Among the wide literature on polynomial kernelization, we only recall here the two following tools used in this paper: compositions (used to prove that a parameterized problem does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$), and polynomial parameter transformations from $L_1$ to $L_2$, denoted by $L_1 \le _{\textsc {ppt}} L_2$ (used to prove that a polynomial kernel for $L_2$ implies a polynomial kernel for $L_1$).

Definition 1

[2] An or-composition algorithm for a parameterized problem $L \subseteq \varSigma ^* \times \mathbb {N}$ is an algorithm that

• receives as input a sequence $((x_1,k), \ldots ,(x_t ,k))$, with $(x_i,k) \in \varSigma ^* \times \mathbb {N}$ for each $1 \le i \le t$,

• uses time polynomial in $\sum _{i=1}^t |x_i|+k$, and

• outputs $(y,k') \in \varSigma ^* \times \mathbb {N}$ such that

  • 1. $(y,k) \in L$ if and only if $(x_i ,k) \in L$ for some $1 \le i \le t$.

  • 2. $k'$ is polynomially bounded by a function of k.

We can similarly define an and-composition algorithm.

A parameterized problem admitting a or-composition (resp. and-composition) is called an or-compositional (resp. and-compositional) problem. We first need the notion of polynomial equivalence relation, defined as an equivalence relation R on $\varSigma ^*$ such that testing whether two strings x, y are equivalent can be done in time polynomial in $|x|+|y|$, and such that R restricted to the strings of size at most n has at most p(n) equivalence classes, for some polynomial p.

Definition 2

[4] Let $L \subseteq \varSigma ^*$ be a (classical) problem and $Q \subseteq \varSigma ^* \times \mathbb {N}$ be a parameterized problem. We say that Lor-cross-composes (resp. and-cross-composes) into Q if there exists a polynomial equivalence relation R and an algorithm A, called the cross-composition, satisfying the following conditions. The algorithm A takes as input a sequence of strings $x_1, \ldots ,x_t \in \varSigma ^*$ that are equivalent with respect to R, runs in time polynomial in $\sum _{i=1}^t|x_i|$, and outputs one instance $(y,k) \in \varSigma ^* \times \mathbb {N}$ such that:

• $k \le p(\max _{i=1}^t |x_i| + \log (t))$ for some polynomial $p(\cdot )$, and

• $(y, k) \in Q$ if and only if there exists at least one index i such that $x_i \in L$ (resp. if for every $i \in [t], x_i \in L$).

Compositions are a great tool to get negative results for kernelization.

Theorem 1

[7, 13] Let L be an or-compositional or an and-compositional parameterized problem whose derived classical problem is NP-complete. Then, L does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

A polynomial compression of a parameterized language $Q \subseteq \varSigma ^* \times \mathbb {N}$ into a language $R \subseteq \varSigma ^*$ is an algorithm that takes as input an instance $(x,k) \in \varSigma ^* \times \mathbb {N}$, works in time polynomial in $|x|+k$, and returns a string y such that $|y| \le p(k)$ for some polynomial p, and $y \in R$ if and only if $(x,k) \in Q$.

Theorem 2

[7, 13] Assume that an NP-hard language L cross-composes into a parameterized language Q. Then Q does not admit a polynomial compression unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

Note that as a polynomial kernel is also a polynomial compression, the previous theorem also rules out the existence of a polynomial kernel.

Definition 3

[5] Let P and Q be parameterized problems. We say that P is polynomial time and parameter reducible to Q, written $P\le _{\textsc {ppt}} Q$, if there exist a polynomial time computable function $f:\varSigma ^* \times \mathbb {N} \rightarrow \varSigma ^* \times \mathbb {N}$ and a polynomial p, such that for all $x \in \varSigma ^*$ and $k \in \mathbb {N}$, if $f(x,k) = (x',k')$, then the following hold:

• $(x,k) \in P$, if and only if $(x',k') \in Q$, and

• $k' \le p(k)$.

We call f a polynomial time and parameter transformation from P to Q (PPT for short).

The following theorem can be used to obtain either positive or negative results.

Theorem 3

[5] Let P and Q be parameterized problems, and suppose that $P_c$ and $Q_c$ are the derived classical problems. Suppose that $Q_c$ is NP-complete, and that $P_c \in$NP. Suppose that $P \le _{\textsc {ppt}} Q$. If Q has a polynomial kernel, then P has a polynomial kernel.

3 A Polynomial Kernel for VC/c-tdmod on General Graphs

In this section we prove that for any positive integer c, VC/c-tdmod admits a polynomial kernel on general graphs. Recall that this was only known for VC/1-tdmod and VC/2-tdmod, as for $c=1$ this corresponds to the standard parameterization and we can use the linear kernel of [1], and for $c=2$ we have 1-twmod$\le 2$-tdmod (as a 1-twmod corresponds to the distance to a forest, while 2-tdmod corresponds to the distance to a star forest), and thus we can use the polynomial kernel of [21] for VC/1-twmod. We also recall that we cannot expect to extend our result to VC/c-twmod for any $c \ge 2$ [8].

As VC/c-tdmod and IS/c-tdmod are equivalent for this parameterization (because any n-vertex graph has vertex cover of size at most k if and only if it has an independent set of size at least $n-k$), we provide the result for IS/c-tdmod. More specifically, in Sect. 3.1 we provide a polynomial kernel for a-c-tdmod-IS, an annotated version of our problem defined below, and in Sect. 3.2 we derive a polynomial kernel for IS/c-tdmod.

3.1 A Polynomial Kernel for a-c-tdmod-IS/$(|X|+|\mathcal {H}|)$

We will find a polynomial kernel for the following annotated version of IS on hypergraphs. Working with hypergraphs is useful because we will use a reduction rule identifying a subset $X'$ of the modulator that cannot be entirely contained in a solution; this will be modeled by adding a hyperedge on the vertex set $X'$.

Throughout this subsection $I=(G,X,k)$ denotes the input of a-c-tdmod-IS with $G=(V,E,\mathcal {H})$ and $V = X \uplus R$. Note that G[X] is a hypergraph and that G[R] is a graph, and that the parameter we consider here is $|X|+|\mathcal {H}|$. For any $X' \subseteq X$ and $R' \subseteq R$, observe that the notation $N_{R'}(X')$ is not ambiguous and denotes $\{v \in R' \mid \exists x \in X' \text{ with } \{x,v\} \in E \}$.

We use the following definition that was introduced in [21] for VC/1-twmod.

Definition 4

[21] Given $X' \subseteq X$ and $R' \subseteq R$, let $\mathsf{conf} _{R'}(X') = \alpha (R')-\alpha (R'{\setminus } N_{R'}(X'))$ be the conflicts induced by $X'$ on $R'$.

Intuitively, $\mathsf{conf} _{R'}(X')$ measures the loss in the size of a maximum independent set of $R'$ due to $X'$. We extend the previous definition in the following way: for any $R' \subseteq R$ and any $Y' \subseteq R'$, let $\mathsf{conf} _{R'}(Y') = \alpha (R')-\alpha (R'{\setminus } Y')$. Note that $\mathsf{conf} _{R'}(X')$ describes the impact of having $X'$ in the independent set, while $\mathsf{conf} _{R'}(Y')$ describes the impact of forbidding $Y'$ in the independent set. We can see that $\mathsf{conf} _{R'}(Y')=0$ is equivalent to the existence of an independent set $S^* \subseteq R'$ such that $|S^*|=\alpha (R')$ and $S^* \cap Y' = \emptyset$.

Lemma 1

Let $R' \subseteq R$ be a connected component of R. If $\mathsf{conf} _{R'}(Y')>0$, there exists $\bar{Y'} \subseteq Y'$ such that $\mathsf{conf} _{R'}(\bar{Y'})>0$ and $|\bar{Y'}| \le f(c)$ with $f(c)=2^c$.

Proof

As it holds that $\mathsf{td}(R')\le c$, let us consider a treedepth decomposition of $R'$ with root r and $t \ge 1$ subtrees rooted at the children of t, where $A_i$, $i \in [t]$ is the vertex set of subtree i. We can partition $Y' = \bigcup _{i \in [t+1]}Y'_i$ with $Y'_i \subseteq A_i$ for $i \in [t]$, $Y'_{t+1} \subseteq \{r\}$, where the $Y'_i$’s are possibly empty. We will prove the lemma by induction on c. Observe that $\sum _{i \in [t]} \alpha (A_i) \le \alpha (R') \le 1+\sum _{i \in [t]} \alpha (A_i)$, and thus we distinguish two cases according to the value of $\alpha (R')$.

Case 1$\alpha (R')=1+\sum _{i \in [t]} \alpha (A_i)$. In this case every maximum independent set $S^*$ of $R'$ contains r. Hence for every $i \in [t]$, $S^* \cap A_i$ is a maximum independent set in $A_i {\setminus } N_{A_i}(r)$, and thus $\alpha (A_i {\setminus } N_{A_i}(r)) = \alpha (A_i)$. Indeed, if we had $\alpha (A_i {\setminus } N_{A_i}(r)) < \alpha (A_i)$ for some i, then $|S^*|$ would be strictly smaller than $1+\sum _{i \in [t]} \alpha (A_i)$.

If $r \in Y'$ (i.e., if $Y'_{t+1} \ne \emptyset$) then we can take $\bar{Y'}=\{r\}$ (as every optimal solution of $R'$ must contain r we get $\alpha (R' {\setminus } \{r\}) < \alpha (R')$, and $|\bar{Y'}|=1 \le 2^c$), and thus we suppose henceforth that $Y'_{t+1} = \emptyset$.

We claim that there exists $i_0 \in [t]$ such that $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(Y'_{i_0}) > 0$. Indeed, otherwise we could define for every $i \in [t]$ an independent set $S_i \subseteq A_i {\setminus } N_{A_i}(r)$ with $|S_i|=\alpha (A_i {\setminus } N_{A_i}(r)) = \alpha (A_i)$ and $S_i \cap Y'_i = \emptyset$. Thus, $S^*=\{r\} \cup _{i \in [t]} S_i$ would be an independent set of size $\alpha (R')$, and as $Y'_{t+1} = \emptyset$ we would have $S^* \cap Y' = \emptyset$, a contradiction to the hypothesis that $\mathsf{conf} _{R'}(Y')>0$. Thus, there exists $i_0 \in [t]$ such that $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(Y'_{i_0}) > 0$, and as $\mathsf{td}(A_{i_0} {\setminus } N_{A_{i_0}}(r)) < c$, by induction hypothesis there exists $\bar{Y'_{i_0}} \subseteq Y'_{i_0}$ such that $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(\bar{Y'_{i_0}}) > 0$ and $|\bar{Y'_{i_0}}| \le 2^{c-1}$. Let us verify that $\bar{Y'} = \bar{Y'_{i_0}}$ satisfies $\mathsf{conf} _{R'}(\bar{Y'})>0$. Let $S^*$ be an independent set of $R'$ with $S^* \cap \bar{Y'} = \emptyset$. If $r \notin S^*$ then clearly $|S^*| < \alpha (R')$. Otherwise, $|S^*| = (\sum _{i \in [t]} |S^* \cap (A_i {\setminus } N_{A_i}(r))|)+1 \le \alpha (A_{i_0} {\setminus } N_{A_{i_0}}(r))-1 + (\sum _{i \in [t], i \ne i_0} \alpha (A_i {\setminus } N_{A_i}(r)))+1 < \alpha (R')$.

Case 2$\alpha (R')=\sum _{i \in [t]} \alpha (A_i)$. In this case there exists $i_0 \in [t]$ such that $\mathsf{conf} _{A_{i_0}}(Y'_{i_0})>0$. Indeed, otherwise we could define for every $i \in [t]$ an independent set $S_i \subseteq A_i$ with $|S_i| = \alpha (A_i)$ and $S_i \cap Y'_i = \emptyset$, and the existence of $S^* = \cup _{i \in [t]}S_i$ would be a contradiction to the hypothesis that $\mathsf{conf} _{R'}(Y')>0$. Thus, by the induction hypothesis there exists $\bar{Y'_{i_0}} \subseteq Y'_{i_0}$ such that $\mathsf{conf} _{A_{i_0}}(\bar{Y'_{i_0}}) > 0$ and $|\bar{Y'_{i_0}}| \le 2^{c-1}$.

If $r \in Y'$ (i.e., if $Y'_{t+1} \ne \emptyset$) then we can take $\bar{Y'}=\bar{Y'_{i_0}} \cup \{r\}$. Let us verify that $\mathsf{conf} _{R'}(\bar{Y'})>0$. Let $S^*$ be an independent set of $R'$ with $S^* \cap \bar{Y'} = \emptyset$. As $S^*$ cannot contain r we have $|S^*| = \sum _{i \in [t]} |S^* \cap A_i| < \alpha (A_{i_0}) + \sum _{i \in [t], i \ne i_0} |S^* \cap A_i| = \alpha (R')$. Thus, we suppose from now on

$$\begin{aligned} \text {Property } \mathbf {p_1}: Y'_{t+1} = \emptyset . \end{aligned}$$

Note that in this case (when $\mathbf {p_1}$ is true) we cannot simply set $\bar{Y'} = \bar{Y'_{i_0}}$, as shown in the example depicted in Fig. 1. Indeed, in this example we would have $\bar{Y'}=\bar{Y'_{i_0}}=\{c_1\}$, however $\mathsf{conf} _{R'}(\{c_1\})=0$ as $S^*=\{b_1,v_1,c_2,v_2\}$ verifies $|S^*|=\alpha (R')$ and $S^* \cap \{c_1\} = \emptyset$.

Properties related to$\alpha$ Let us prove that we can always assume the following

$$\begin{aligned} \text {Property}\ \mathbf {p_2}: \text {for every}\ i \ne i_0, \alpha (A_i {\setminus } N_{A_i}(r)) = \alpha (A_{i}). \end{aligned}$$

Indeed, if $\mathbf {p_2}$ is not true, then there exists $i_1 \ne i_0$, $i_1 \in [t]$ such that $\alpha (A_{i_1} {\setminus } N_{A_{i_1}}(r)) < \alpha (A_{i_1})$, and we set $\bar{Y'}=\bar{Y'_{i_0}}$. Let $S^*$ be an independent set of $R'$ with $S^* \cap \bar{Y'} = \emptyset$. If $r \notin S^*$ then as previously $|S^*| < \alpha (R')$, otherwise we get $|S^*| \le \alpha (A_{i_0})-1+\alpha (A_{i_1})-1+ (\sum _{i \in [t],i \ne i_0, i \ne i_1} \alpha (A_i))+1< \alpha (R')$. Thus, we now assume $\mathbf {p_2}$. Let us now prove the following

$$\begin{aligned} \text {Property}\ \mathbf {p'_2}: \alpha (A_{i_0} \cup \{r\}) = \alpha (A_{i_0}). \end{aligned}$$

By contradiction, suppose that there exists an independent set $S_1^*$ of $A_{i_0} \cup \{r\}$ containing r such that $|S_1^*| = \alpha (A_{i_0})+1$. According to $\mathbf {p_2}$, for every $i \ne i_0$ there exists an independent set $S_i$ of $A_i {\setminus } N_{A_i}(r)$ of size $\alpha (A_i)$, and thus $\alpha (R') > \sum _{i \in [t]} \alpha (A_i)$, a contradiction. Thus, we now assume $\mathbf {p'_2}$.

Properties related to$\mathsf{conf} _{A_i}(Y'_i)$ Let us prove than we can assume the following

$$\begin{aligned} \text {Property}\ \mathbf {p_3}: \text {for every}\ i \ne i_0, \mathsf{conf} _{A_i {\setminus } N_{A_i}(r)}(Y'_i)=0. \end{aligned}$$

Indeed, if $\mathbf {p_3}$ is not true we can get the desired result as follows. Let $i_1 \ne i_0$, $i_1 \in [t]$ such that $\mathsf{conf} _{A_{i_1} {\setminus } N_{A_{i_1}}(r)}(Y'_{i_1})>0$. We use the same arguments as in the previous paragraph and define $\bar{Y'}= \bar{Y'_{i_0}} \cup \bar{Y'_{i_1}}$. Note that $|\bar{Y'}| \le |\bar{Y'_{i_0}}|+|\bar{Y'_{i_1}}| \le 2^c$. Using the same notation, if $r \notin S^*$ then $|S^*| = (\sum _{i \in [t]} |S^* \cap A_i|) \le \alpha (A_{i_0})-1 + (\sum _{i \in [t], i \ne i_0} \alpha (A_i))< \alpha (R')$, and otherwise $|S^*| = (\sum _{i \in [t]} |S^* \cap (A_i {\setminus } N_{A_i}(r))|)+1 \le \alpha (A_{i_0})-1 + \alpha (A_{i_1})-1 + (\sum _{i \in [t], i \ne i_0, i \ne i_1} \alpha (A_i))+1 < \alpha (R')$. Thus, we now assume $\mathbf {p_3}$. Note that $\mathbf {p_2}$ and $\mathbf {p_3}$ imply

$$\begin{aligned} \text {Property}\ \mathbf {p'_3}: \text {for every}\ i \ne i_0, \mathsf{conf} _{A_i}(Y'_i)=0. \end{aligned}$$

Case 2a There does not exist a maximum independent set $S^*$ of $R'$ such that $r \in S^*$. In this case, we set $\bar{Y'} = \bar{Y'_{i_0}}$. Let us prove that $\mathsf{conf} _{R'}(\bar{Y'})>0$. Let $S^*$ be a maximum independent set of $R'$ with $S^* \cap \bar{Y'} = \emptyset$. As $r \notin S^*$, we get $|S^*| = \sum _{i \in [t]} |S^* \cap A_i| \le \alpha (A_{i_0})-1+ \sum _{i \in [t], i \ne i_0} \alpha (A_i) < \alpha (R')$.

Case 2b There exists a maximum independent set $S^*$ of $R'$ such that $r \in S^*$. This implies that $\alpha (A_{i_0} {\setminus } N_{A_{i_0}}(r))=\alpha (A_{i_0})-1$. Let us prove that $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(Y'_{i_0})>0$. If it was not the case, there would exist an independent set $S^*_{i_0}$ of $A_{i_0} {\setminus } N_{A_{i_0}}(r)$ of size $\alpha (A_{i_0} {\setminus } N_{A_{i_0}}(r))=\alpha (A_{i_0})-1$ such that $S^*_{i_0} \cap Y'_{i_0} = \emptyset$. By $\mathbf {p_3}$, there would exist, for every $i \ne i_0$, an independent set $S^*_i$ of $A_i {\setminus } N_{A_i}(r)$ of size $\alpha (A_i {\setminus } N_{A_i}(r))=\alpha (A_i)$ (by $\mathbf {p_2}$) such that $S^*_i \cap Y'_i = \emptyset$. Thus, $S^*=\{r\} \cup (\bigcup _{i \in [t]}S^*_i)$ would be an independent set of size $\alpha (R')$ such that $S^* \cap Y' = \emptyset$ (recall that by $\mathbf {p_1}$, $r \notin Y'$), a contradiction. Thus, we know that both $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(Y'_{i_0})>0$ and $\mathsf{conf} _{A_{i_0}}(Y'_{i_0})>0$ (which was established at the beginning of Case 2). Using twice the induction hypothesis we get that there exists $\bar{Y'_{i_0}}^1 \subseteq Y'_{i_0}$ such that $\mathsf{conf} _{A_{i_0} {\setminus } N_{A_{i_0}}(r)}(\bar{Y'_{i_0}}^1)>0$ and there exists $\bar{Y'_{i_0}}^2 \subseteq Y'_{i_0}$ such that $\mathsf{conf} _{A_{i_0}}(\bar{Y'_{i_0}}^2)>0$, with both $|\bar{Y'_{i_0}}^1|$ and $|\bar{Y'_{i_0}}^2|$ bounded by $2^{c-1}$. Thus, we set $\bar{Y'}=\bar{Y'_{i_0}}^1 \cup \bar{Y'_{i_0}}^2$. Let us verify that $\mathsf{conf} _{R'}(\bar{Y'})>0$. Let $S^*$ be an independent set of $R'$ with $S^* \cap \bar{Y'} = \emptyset$. If $r \in S^*$, then $|S^*| = \sum _{i \in [t]} |S^* \cap (A_i {\setminus } N_{A_i}(r))| + 1 = \alpha (A_{i_0} {\setminus } N_{A_{i_0}}(r))-1 + \sum _{i \in [t],i \ne i_0}\alpha (A_i) + 1= \alpha (A_{i_0})-2 + \sum _{i \in [t],i \ne i_0}\alpha (A_i) + 1 < \alpha (R')$. Otherwise, $|S^*| = \sum _{i \in [t]} |S^* \cap A_i| = \alpha (A_{i_0})-1 + \sum _{i \in [t],i \ne i_0}\alpha (A_i) < \alpha (R')$. $\square$

Fig. 1

a Example of a graph $G[R']$ (left) with an associated treedepth decomposition (right) as used in Lemma 1, with $Y'=\{c_1,c_2\}$. This case corresponds to one of the subcases of Case 2, as $\alpha (R')=\alpha (A_1)+\alpha (A_2)=4$, $\mathsf{conf} _{A_1}(Y'_1)>0$, $\mathsf{conf} _{A_2}(Y'_2)=0$. Moreover, $\mathbf {p_2}$ and $\mathbf {p'_2}$ are true, while $\mathbf {p_3}$ is false (but $\mathbf {p'_3}$ is true). b Example for $t=2$ of the construction of Lemma 2, where the circled vertices belong to S

A first lower bound on the function f of Lemma 1 can be obtained by considering a clique $R'$ on c vertices (hence, with $\mathsf{td}(R')=c$) and $Y'=R'$, as every $\bar{Y'} \subsetneq Y'$ satisfies $\mathsf{conf} _{R'}(\bar{Y'})=0$. However, as shown in Lemma 2 below, we can even obtain an exponential lower bound, showing that the function $f(c) = 2^c$ of Lemma 1 is almost tight.

Lemma 2

There exists a constant $\lambda$ such that for every $c\ge \lambda$ there exists a graph $G=(R,E)$ and $Y \subseteq R$ such that $\mathsf{td}(G)=c$, $|Y| \ge 2^{c-3}$, $\mathsf{conf} _{R}(Y)>0$, and for every $\bar{Y} \subsetneq Y$, $\mathsf{conf} _{R}(\bar{Y})=0$.

Proof

Given an integer t, let $G=(R,E)$ with $R = \bigcup _{i\in [2t]}\{a_i,b_i,c_i \} \cup \{v_1,v_2\}$ and $E=\bigcup _{i \in [2t]}\{\{a_i,b_i\},\{c_i,a_i\},\{c_i,b_i\}\} \cup \bigcup _{i \in [t]}\{b_{2i-1},b_{2i}\} \cup \bigcup _{i \in [t-1]}\{a_{2i},a_{2i+1}\} \cup \{v_1,a_1\} \cup \{a_{2t},v_2\}$ (G is a path on $2t+2$ vertices); see Fig. 1a for an example for $t=1$. We would like to point out that R corresponds to the edge gadget of [8], except that we removed some edges (namely, $\{a_{2i-1},a_{2i}\}$) to lower its treedepth by a factor 2. Let $Y = C$.

We have $\alpha (R) = 2t+2$, and $\alpha (R {\setminus } Y) = \alpha (R)-1 < \alpha (R)$. Let $\bar{Y} \subsetneq Y$, and let $i_0$ such that $c_{i_0} \notin \bar{Y}$. By symmetry, we can suppose that $i_0$ is even with $i_0=2i'_0$. Let $S = \{v_1,v_2\} \cup \bigcup _{i \in [i'_0-1]}\{b_{2i-1},a_{2i}\} \cup \{b_{2i'_0-1},c_{2i'_0}\} \cup \bigcup _{i \in [i'_0+1,t]}\{a_{2i-1},b_{2i}\}$; see Fig. 1b for an example for $t=2$. As S is an independent set of size $\alpha (R)$ with $S \cap \bar{Y}=\emptyset$, we get that $\mathsf{conf} _{R}(\bar{Y})=0$.

Observe also that $\mathsf{td}(R) \le \log (t)+3$. Indeed, the treedepth of the initial path $P_{2t+2}$ on $2t+2$ vertices is at most $\lceil \log (2t+3) \rceil \le \log (t)+2$, for t large enough. Then, $\mathsf{td}(R) \le \mathsf{td}(P_{2t+2})+1$ as for every $i \in [2t]$, we can add to the treedepth decomposition of $P_{2t+2}$ a vertex $c_i$ as a new leaf attached to the lowermost vertex of $\{a_i,b_i\}$ in the decomposition. $\square$

Observation 1

Lemma 1 was proven in [21] when $R'$ is a forest and $|\bar{Y'}| \le 2$. Even if we already know that IS/2-twmod does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [8], it remains interesting to observe that, in particular, this lemma becomes false for 2-twmod, as the graph of Lemma 2 has treewidth 2. This points out one crucial difference between c-treewidth and c-treedepth modulators.

Let us now start the description of the kernel for a-c-tdmod-IS/$(|X|+|\mathcal {H}|)$. Given an input (G, X, k) of a-c-tdmod-IS, we define the following three rules. Note that these rules and definitions (and the associated safeness proofs) correspond to Rules 1, 2, and 3 of [21], except that we now bound the sizes of the subsets by a function f(c) instead of by 2.

Definition 5

Given an input (G, X, k) of a-c-tdmod-IS (with $\mathsf{td}(G[R]) \le c$ where $R = V {\setminus } X$), the chunks of the input are defined by $\mathcal {X}= \{X' \subseteq X \mid \text{ there } \text{ is } \text{ no } H \in \mathcal {H} \text{ such } \text{ that } H \subseteq X', \text{ and } 0 < |X'| \le f(c)\}$, where $f(c)=2^c.$

Intuitively, the chunks correspond to all possible small traces of an independent set of G in X. We are now ready to define the first two rules.

Reduction Rule 1 If there exists $u \in X$ such that $\mathsf{conf} _R(\{u\}) > |X|$, remove u from the graph.

Reduction Rule 2 If there exists $X' \in \mathcal {X}$ such that $\mathsf{conf} _R(X') > |X|$, add $X'$ to $\mathcal {H}$.

Lemma 3

Rules 1 and 2 are safe: if $I=(G,X,k)$ is the original input of a-c-tdmod-IS and $I^1=(G^1,X^1,k)$ is the input after the application of Rule 1 or Rule 2, then I and $I^1$ are equivalent.

Proof

Let us only prove the safeness of Rule 2, as Rule 1 corresponds to Rule 2 using $X' = \{u\}$. Indeed, adding hyperedge $\{u\}$ is equivalent to removing u, as by definition no independent set could contain u anymore. Let us prove that $\alpha (G) \ge k$ implies that $\alpha (G^1) \ge k$. Let S be an independent set of G of size at least k. If $X' \nsubseteq S$ then S is also an independent set of $G^1$ of size k. Otherwise, let $S^1$ be an independent set of R of size $\alpha (R)$. Observe that $k \le |S| = |S \cap X|+|S \cap R| < |X|+(\alpha (R)-|X|) = |S^1|$ (the strict inequality holds as $\mathsf{conf} _R(X')>|X|$), and we get the desired result. $\square$

Reduction Rule 3 If R contains a connected component $R'$ such that for every $X' \in \mathcal {X}$, $\mathsf{conf} _{R'}(X')=0$, delete $R'$ from the graph and decrease k by $\alpha (R')$.

To prove that Rule 3 is safe we need the following lemma. Recall that we say that $X' \subseteq X$ is an independent set if and only if there is no $H \in \mathcal {H}$ such that $H \subseteq X'$.

Lemma 4

Let $I=(G,X,k)$ be an instance of a-c-tdmod-IS. Let $R'$ be a connected component of R. If there exists an independent set $X' \subseteq X$ such that $\mathsf{conf} _{R'}(X') > 0$, then there exists $\bar{X'} \in \mathcal {X}$ such that $\mathsf{conf} _{R'}(\bar{X'}) > 0$.

Proof

Let $Y' = N_{R'}(X')$. As $\mathsf{conf} _{R'}(X') > 0$, $\mathsf{conf} _{R'}(Y') > 0$. By Lemma 1, there exists $\bar{Y'} \subseteq Y'$ such that $\mathsf{conf} _{R'}(\bar{Y'})>0$ and $|\bar{Y'}| \le f(c)$. For every $y' \in \bar{Y'}$, there exists a vertex $g(y') \in X'$ such that $\{g(y'),y'\} \in E$, and thus we define $\bar{X'}=\cup _{y' \in \bar{Y'}}g(y')$. As $\bar{X'} \subseteq X'$, $\bar{X'}$ is still an independent set, and $|\bar{X'}| \le |\bar{Y'}| \le f(c)$, we get that $\bar{X'} \in \mathcal {X}$. $\square$

Lemma 5

Rule 3 is safe: if $I=(G,X,k)$ is the original input of a-c-tdmod-IS and $I'=(G',X',k')$ is the input after the application of Rule 3, then I and $I'$ are equivalent.

Proof

$\alpha (G) \ge k \Rightarrow \alpha (G') \ge k'=k-\alpha (R')$ is straightforward, as if S is an independent set of G of size at least k then $S {\setminus } R'$ is an independent set of $G'$ of size at least $k-\alpha (R')$.

$\alpha (G) \ge k \Leftarrow \alpha (G') \ge k'=k-\alpha (R')$: Let $S'$ be an independent set of $G'$ of size at least $k'$. As Rule 3 applied, we know that for every $X_1 \subseteq \mathcal {X}$, $\mathsf{conf} _{R'}(X_1)=0$. Using the contrapositive of Lemma 4, it follows that for every independent set $X_1 \subseteq X$, $\mathsf{conf} _{R'}(X_1) = 0$. In particular we get that $X_S = S' \cap X$ verifies $\mathsf{conf} _{R'}(X_S)=0$. Thus, there exists an independent set $S_{R'}$ of $G[R']$ of size $\alpha (R')$ and such that $N_{R'}(X_S) \cap S_{R'} = \emptyset$, and thus $S' \cup S_{R'}$ is an independent set of G of size at least k. $\square$

Lemma 6

Let $I=(G,X,k)$ be an instance of a-c-tdmod-IS, and let s be the number of connected components of $R=V {\setminus } X$. If none of Rule 1, Rule 2 and Rule 3 can be applied, then $s = \mathcal {O}(|X|^{f(c)+2})$, where f is the function of Lemma 1.

Proof

First, as Rule 1 and Rule 2 cannot be applied, we have $\sigma =\sum _{X' \in \mathcal {X}} \mathsf{conf} _R(X') \le \sum _{i=1}^{f(c)} {|X| \atopwithdelims ()i}|X|=\mathcal {O}(|X|^{f(c)+2})$. On the other side, as Rule 3 cannot be applied, for every connected component $R' \subseteq R$ there exists $X' \in \mathcal {X}$ such that $\mathsf{conf} _{R'}(X')>0$, and thus we have $\sigma \ge s$, implying the desired result. $\square$

We are now ready to present in Algorithm 1 our polynomial kernel for a-c-tdmod-IS.

Theorem 4

For every fixed integer $c \ge 0$, Algorithm 1 is a polynomial kernel for a-c-tdmod-IS/$(|X|+|\mathcal {H}|)$. More precisely, for every input $I=(G,X,k)$ (with $G = (V,E,\mathcal {H})$, $R=V{\setminus } X$) where X is a c-treedepth modulator, Algorithm 1 produces an equivalent instance $\tilde{I}=(\tilde{G},\tilde{X},\tilde{k})$ (with $\tilde{G} = (\tilde{V},\tilde{E},\tilde{H})$, $\tilde{R}=\tilde{V}{\setminus } \tilde{X}$) where $|\tilde{X}| = \mathcal {O}(|X|^{2^{(c+1)(c+2)/2}})$, $|\tilde{\mathcal {H}}| = |\mathcal {H}| + \mathcal {O}(|X|^{2^{(c+1)(c+2)/2}})$, and $\tilde{R} = \emptyset$.

Proof

Observe first that Algorithm 1 is polynomial for fixed c. Indeed, computing $\mathsf{conf} _{R'}(X')$ is polynomial (as $\mathsf{tw}(R') \le \mathsf{td}(R')$ and it is well-known that IS/$\mathsf{tw}$ is FPT [6]) and there are at most $\mathcal {O}(|X|^c)$ applications of Rules 1 and 2, and $\mathcal {O}(s|X|^c)$ applications of Rule 3. Moreover, an optimal treedepth decomposition of each connected component can be computed in FPT time parameterized by c, using [26] or [31]. Let us prove the result by induction on c. The result is trivially true for $c=0$. Let us suppose that the result holds for $c-1$ and prove it for c. Observe that $X'$ is now a $(c-1)$-treedepth modulator, and thus we can apply the induction hypothesis on $A(I',c-1)$. For every $\ell \in [3]$, let $I_\ell =(G_\ell ,X_\ell ,k_\ell )$ with $G_\ell =(V_\ell ,E_\ell ,\mathcal {H}_\ell )$ and $R_\ell =V_\ell {\setminus } X_\ell$ denote the instance after exhaustive application of Rule $\ell$, respectively.

Equivalence of the output By Lemma 3 and Lemma 5, we know that Rules 1, 2, and 3 are safe, and thus that I and $I_3$ are equivalent. Note that $I_3$ is equivalent to $I'$ as the underlying input is the same (except that some vertices were added to the modulator). As using induction hypothesis $A(I',c-1)$ outputs an instance $\tilde{I}$ equivalent to $I'$, we get the desired result.

Size of the output We have

• $|X_1| \le |X|$, $|\mathcal {H}_1|=|\mathcal {H}|$.

• $|X_2| = |X_1|$, $|\mathcal {H}_2| \le |\mathcal {H}_1|+|X_1|^{f(c)}$.

• $|X_3| = |X_2|$, $|\mathcal {H}_3| = |\mathcal {H}_2|$. By Lemma 6, s, the number of connected components of $R_3$, verifies $s = \mathcal {O}(|X_3|^{f(c)+2})$.

• $|X'| \le |X_3| + s$, and $|\mathcal {H}'| \le |\mathcal {H}_3|+s|X_3|$.

Thus we get $|X'| = \mathcal {O}(|X|^{f(c)+2}) = \mathcal {O}(|X|^{2^{c+1}})$ and $|\mathcal {H}'| = |\mathcal {H}| + \mathcal {O}(|X|^{f(c)+3})$. Using induction hypothesis we get that $|\tilde{X}| = \mathcal {O}(|X'|^{2^{c(c+1)/2}}) = \mathcal {O}(|X|^{2^{(c+1)(c+2)/2}})$, and that $|\tilde{\mathcal {H}}| = |\mathcal {H}'|+ \mathcal {O}(|X'|^{2^{c(c+1)/2}}) = |\mathcal {H}| + \mathcal {O}(|X|^{2^c+3})+\mathcal {O}(|X|^{2^{(c+1)(c+2)/2}}) = |H|+\mathcal {O}(|X|^{2^{(c+1)(c+2)/2}})$, as claimed. $\square$

3.2 Deducing a Polynomial Kernel for IS/c-tdmod

Observe first that we can suppose that the modulator is given in the input, i.e., that IS/c-tdmod$\le _{\textsc {ppt}}$c-tdmod-IS/|X| ($\le _{\textsc {ppt}}$ is defined in Definition 3). Indeed, given an input (G, x, k) of IS/c-tdmod (where x denotes the size of a c-treedepth modulator), using the $2^c$-approximation algorithm of [18] for computing a c-treedepth modulator, wet get in polynomial time a set X such that $|X| \le 2^c \cdot x$ and $\mathsf{td}(R) \le c$, where $R=V{\setminus } X$.

Observe also that IS/$|X| \le _{\textsc {ppt}}$ a-c-tdmod-IS/$(|X|+|\mathcal {H}|)$ using the same set X and with $|\mathcal {H}| \le |X|^2$. Now, as usual when using bikernels, we could claim that as IS is Karp $\mathsf{NP}$-hard and as a-c-tdmod-IS is in $\mathsf{NP}$, there exists a polynomial reduction from a-c-tdmod-IS, implying the existence of a polynomial kernel for IS/c-tdmod. However, let us make such a reduction explicit to provide an explicit bound on the size of the kernel.

Lemma 7

Let $I=(G,k)$ with $G=(X,\mathcal {H})$ be an instance of a-c-tdmod-IS as produced by Theorem 4 (as $R= \emptyset$ the set of vertices is reduced to X, and $\mathcal {H}$ is a set of hyperedges on X). We can build in polynomial time an equivalent instance $I'=(G',k')$ of IS with $G'=(V',E')$ where $|V'| \le \mathcal {O}(|X| \cdot |\mathcal {H}|)$.

Proof

Let $n = |X|$, $X = \{v_i \mid i \in [n]\}$ and $m = |\mathcal {H}|$. We refer the reader to Fig. 2 for an example of the construction of $G'$. For every $i \in [n]$, we add to $G'$ the vertex gadget constituted of $V'_i = \{y^a_i,y^b_i,z_i\}$ and edges $\{z_i,y^a_i\}$ and $\{z_i,y^b_i,\}$. Taking vertices $y^a_i$ and $y^b_i$ in a solution for $I'$ will correspond to taking $v_i$ in the corresponding solution of I. For every $H \in \mathcal {H}$, we add to $G'$ the edge gadget $W'_H = \bigcup _{\ell \in [|H|]}W'^\ell _H$, where each $W'^\ell _H$ is an independent set of size n, and we add edges to make $G[W'_H]$ a complete |H|-partite graph with ${|H| \atopwithdelims ()2} n^2$ edges. Finally, for every $H \in \mathcal {H}$, $H=\{v_{H_\ell } \mid \ell \in [|H|]\}$ and $\ell \in [|H|]$, we add edges to make $G[W'^\ell _H \cup \{y^a_{H_\ell },y^b_{H_\ell }\}]$ a complete bipartite graph with 2n edges. Thus, the $\ell$th “column” of $W'_H$ corresponds to the $\ell$th vertex of H. This completes the description of $G'$. Let $k'=n+k+n m$.

Fig. 2

Example of the construction of $G'$ for $n=5$, $m=1$, and $H = \{1,3,4\}$

$\alpha (G) \ge k \Rightarrow \alpha (G') \ge k'$: Without loss of generality let $S=\{v_i \mid i \in [k]\}$ be an independent set of G. For every $H=\{v_{H_\ell } \mid \ell \in [|H|]\}$ there exists $\ell$ such that $v_{H_\ell } \notin S$. We define $S'=\bigcup _{i \in [k]}\{y^a_i,y^b_i\} \cup \bigcup _{i \in [n]{\setminus } [k]}\{z_i\} \cup \bigcup _{H \in \mathcal {H}}W'^{H_\ell }_H$.

$\alpha (G) \ge k \Leftarrow \alpha (G') \ge k'$: Let $S'$ be an independent set of $G'$ of size at least $k'$. We can always assume that for every $H \in \mathcal {H}$ and $\ell \in [|H|]$, if $W'^\ell _H \cap S' \ne \emptyset$ then $W'^\ell _H \subseteq S'$ (as all vertices of $W'^\ell _H$ have the same neighborhood, we can safely add $W'^\ell _H$). Note that there cannot exist $H \in \mathcal {H}$ such that $W'_H \cap S' = \emptyset$. Indeed, otherwise $|S'| \le n(m-1)+2n < k'$.

Thus, for every $H=\{v_{H_\ell } \mid \ell \in [|H|]\}$ there exists (a unique) $\ell _H \in [|H|]$ such that $W'^{\ell _H}_H \subseteq S'$. As there remain $n+k$ vertices to take in the $V'_i$’s, and as $y^a_i$ and $y^b_i$ have the same neighborhood, we get that, without loss of generality, for every $i \in [k]$ we have $\{y^a_{i},y^b_{i}\} \subseteq S'$, and for every $i \in [n]{\setminus } [k]$ we have $z_i \in S'$. Thus, we define $S = \{v_i \mid i \in [k]\}$. Let us verify that S is an independent set. Let $H \in \mathcal {H}$. As $W'^{\ell _H}_H \subseteq S'$ and $S'$ is an independent set, we deduce that there are no edges in $G'$ between $W'^{\ell _H}_H$ and any of the $\{y^a_{i},y^b_{i}\}$ for $i \in [k]$, implying that $v_{H_{\ell _H}} \notin S$, and therefore S is indeed an independent set. $\square$

Putting pieces together we get the main theorem of this section, whose proof is now immediate.

Theorem 5

For every integer $c \ge 1$, IS/c-tdmod (or equivalently, VC/c-tdmod) admits a polynomial kernel on general graphs with $\mathcal {O}\left( x^{2^{\frac{1}{2}(c+1)(c+2)+1}}\right)$ vertices, where x is the size of a c-treedepth modulator.

4 Excluding Polynomial Kernels for DS/c-tdmod on Degenerate Graphs

Given a graph G, we define $G^{c\text {-sub}}$ as the graph obtained from G by subdividing each edge c times. In other words, we add a set $X_e=\{x_e^\ell \mid \ell \in [c]\}$ of c vertices of degree 2 for every edge $e \in E$ of G.

Observation 2

For every $c \ge 0$ and every $k \ge 0$, G has a dominating set of size k if and only if $G^{3c\text {-sub}}$ has a dominating set of size $k+mc$, where m is the number of edges of G.

Proof

Indeed, if S is a dominating set of G of size k, then we construct a dominating set of $G^{3c\text {-sub}}$ of size $k+mc$ by taking S and the following vertices. For every $e = \{u,v\}$ with $u \in S$ and $v \notin S$ we take $\{x_e^{3\ell } \mid 1 \le \ell \le c \}$ (we add to the dominating set every third vertex in the set $X_e$ starting from u). Otherwise (if both or none of $\{u,v\}$ belong to S) we take $\{x_e^{3\ell +2} \mid 0 \le \ell \le c-1 \}$. The other direction is also true, as every solution must include at least c vertices in each $X_e$, and every solution can be modified so that it does not include more than c vertices in each $X_e$. Thus, the k vertices of a solution of $G^{3c\text {-sub}}$ corresponding to original vertices of G form a dominating set of G. $\square$

Let us start with the following proposition, which follows from existing negative results for Dominating Set parameterized by the size of a vertex cover [11].

Proposition 1

DS/c-tdmod does not admit a polynomial kernel on 2-degenerate graphs for every $c \ge 3$, unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

Proof

Let us prove that DS/VC$\le _{\textsc {ppt}}$DS$_{C_{\text {dege}}}$/3-tdmod, where $C_{\text {dege}}$ is the class of 2-degenerate graphs. As DS/VC (and even DS/k+VC) does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [11], we will get the desired result using Theorem 3. Let (G, k) be an instance of DS/VC with $G=(V,E)$ and $m=|E|$. We define $G'=G^{3\text {-sub}}$, and let $V'$ be the set of vertices of $G'$. By Observation 2, G has a dominating set of size k if and only if $G'$ has a dominating set of size $k+m$. Moreover, it is clear that $G'$ is 2-degenerate. Finally, every vertex cover X of G is a 3-treedepth modulator of $G'$. Indeed, in $G'[V'{\setminus } X]$, to each edge $e \in E$ entirely contained in X corresponds in $G'[V'{\setminus } X]$ an isolated $P_3$, and to each $v \in V {\setminus } X$ corresponds in $G'[V' {\setminus } X]$ a spider (that is, a tree with only one vertex of degree more than two) rooted at v of height 4 with $x\ge 1$ leaves. Thus, $G'[V'{\setminus } X]$ is a disjoint collection of $P_3$’s and spiders of height 4, both having treedepth at most 3. As 3-tdmod$(G') \le \mathsf{vc}(G)$ (the size of a minimum vertex cover of G), this is a PPT reduction and we get the desired result. We can get the same result for DS$_{C_{\text {dege}}}$/c-tdmod for $c \ge 4$ by subdividing 3f(c) times each edge of G, for an appropriate function f.$\square$

Observation 3

DS/1-tdmod (or equivalently DS/VC) admits a polynomial kernel on degenerate graphs. Indeed, given an instance (G, k) of DS/VC, we compute in polynomial time a 2-approximate vertex cover X of G. If $|X| \le k$ then we output a trivial Yes-instance, otherwise VC$(G) \ge \frac{k}{2}$ and we can apply the polynomial kernel for DS/k on degenerate graphs of Philip et al. [30].

Thus, by Proposition 1 and Observation 3, the only remaining case for degenerate graphs is DS/2-tdmod. We would like to point out that the composition of [11] for DS/($k+$VC) on general graphs cannot be easily adapted to DS/2-tdmod on degenerate graphs, as for example subdividing each edge also leads to a result for DS/3-tdmod. Thus, we treat the case DS/2-tdmod on degenerate graphs using an ad-hoc reduction.

Theorem 6

DS/2-tdmod does not admit a polynomial kernel on 4-degenerate graphs unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

Proof

We prove this result by using an or-cross-composition from 3-Sat (see Definition 2). We consider t instances of 3-Sat, where for every $i \in [t]$, instance $I^i$ has $m_i$ clauses $\{C^i_j \mid j \in [m_i]\}$ and $n_i$ variables $X^i=\{x^i_{\ell } \mid {\ell } \in [n_i]\}$, each clause containing 3 variables. We can choose the equivalence relation of Definition 2 such that for every $i \in [t]$, we have $m_i=m$ and $n_i=n$.

Let us now construct a graph $G=(V,E)$ as follows; see Fig. 3 for an illustration. We start by adding to V the set of vertices $\mathcal {X}=\bigcup _{{\ell } \in [n]} \{x_{\ell }, \bar{x}_{\ell }\}$ (and thus $|\mathcal {X}|=2n$) and $C^i = \{c^i_{\ell } \mid {\ell } \in [m]\}$ for every $i \in [t]$. Let $C= \bigcup _{i \in [t]} C^i$. For every $i \in [t]$, ${\ell } \in [n]$, $j \in [m]$, we set $\{x_{\ell },c^i_j\}\in E^i$ (resp. $\{\bar{x}_{\ell },c^i_j\}\in E^i$) if and only if $C^i_j$ contains $x^i_{\ell }$ (resp. $\bar{x}^i_{\ell }$). We add to E the set $\bigcup _{i \in [t]} E^i$. Then, we add to V the set $A=\{a_{\ell } \mid {\ell } \in [n]\}$, and create n triangles by adding to E edges $\{x_{\ell },\bar{x}_{\ell }\}$, $\{a_{\ell },x_{\ell }\}$, and $\{a_{\ell },\bar{x}_{\ell }\}$ for every ${\ell } \in [n]$. Finally, we add to V the set $Y= \{y^i \mid i \in [t]\}$, $R= \{r^i \mid i \in [t]\}$, and a vertex $\alpha$. Then, for every $i \in [t]$, we add to E edges $\{r^i,c^i_{\ell } \}$ for every ${\ell } \in [m]$, edges $\{r^i,y^i\}$, and edges $\{y^i,\alpha \}$. This concludes the construction of G. To summarize, G has $3n+t(m+2)+1$ vertices (vertices are partitioned into $V=(\mathcal {X}\cup A) \cup (C\cup Y\cup R) \cup \{\alpha \}$) and, in particular, for every $i \in [t]$, $G[\{r^i\} \cup C^i \cup y^i]$ is a star, and $G[\{\alpha \} \cup Y]$ is also a star.

The or-equivalence Let us prove that there exists $i \in [t]$ such that $I^i$ is satisfiable if and only if G has a dominating set of size at most $k=n+t$. Suppose first, without loss of generality, that $I^1$ is satisfiable, and let $S_{\mathcal {X}} \subseteq \mathcal {X}$ be the set of n literals corresponding to this assignment (thus for every $\ell \in [n]$ we have $|S_\mathcal {X}\cap \{x_{\ell },\bar{x}_{\ell }\}|=1$). Let $S = S_\mathcal {X}\cup y^1 \cup (R {\setminus } \{r^1\})$. We have $|S|=n+t$, and S is a dominating set of G as

• $\mathcal {X}\cup A$ is dominated by $S_\mathcal {X}$,

• $C^1$ is dominated by $S_\mathcal {X}$ as it corresponds to an assignment satisfying $I^1$, and for every $i \in [t], i \ge 2$, $C^i$ is dominated by $r^i$,

• $y^1 \in S$, and for every $i \in [t], i \ge 2$, $y^i$ is dominated by $r^i$,

• $r^1$ is dominated by $y^1$, and for every $i \in [t], r \ge 2$, $r^i \in S$, and

• $\alpha$ is dominated by $y^1$.

For the other direction, let $S = S_1 \cup S_2$, with $S_1 = S \cap (\mathcal {X}\cup A)$, be a dominating set of G of size at most $k=n+t$. Without loss of generality, we can always suppose that $S_1 \subseteq \mathcal {X}$, as if $a_{\ell } \in S$ we can always remove $a_{\ell }$ from S and add (arbitrarily) $x_{\ell }$ or $\bar{x}_{\ell }$.

Let us first prove that $|S_1|=n$. Observe first that $|S_1| \ge n$ as dominating A requires at least n vertices. Suppose now by contradiction that $|S_1| > n$. Then, there would remain at most $t-1$ vertices to dominate R, which is not possible. Note that we even have that for every $\ell \in [n]$, $|S_1 \cap \{x_{\ell },\bar{x}_{\ell }\}|=1$, as every $a^{\ell }$ must be dominated and $|S_2|=t$.

Let us now analyze $S_2$ (recall that, by definition, $S_2 \subseteq (C\cup Y\cup R) \cup \{\alpha \}$). We cannot have that for every $i \in [t]$, $|S_2 \cap (C^i\cup r^i)| \ge 1$, as otherwise there would be no remaining vertex to dominate $\alpha$. Thus, there exists $i_0$ such that $|S_2 \cap (C^{i_0}\cup r^{i_0})|= 0$. This implies that $C^{i_0}$ is dominated by $S_1$. As for every ${\ell } \in [n]$, $|S_1 \cap \{x_{\ell },\bar{x}_{\ell }\}|=1$, $S_1$ corresponds to a valid truth assignment that satisfies all the $C^i_{\ell }$’s, ${\ell } \in [m]$, and the instance $I^{i_0}$ is satisfiable.

Size of the parameter Let $M = \mathcal {X}\cup A\cup \{\alpha \}$. As $G[V {\setminus } M]$ contains t disjoint stars, we have that 2-tdmod$(G) \le |M| \le \text {poly}(n)$, as required.

Degeneracy Let us prove that G is 4-degenerate. Observe that every vertex in $C$ has degree at most 4 (three neighbors in $\mathcal {X}$ and one in $R$). Thus, every ordering of V(G) of the form $(C,R,Y,\alpha ,\mathcal {X},A)$ (with arbitrary order within each set) is a 4-elimination order of G, that is, the vertices of G can be removed according to this ordering so that the current first vertex has at most 4 neighbors in the current graph. $\square$

Fig. 3

Example of the or-cross-composition of Theorem 6

5 Excluding Polynomial Kernels Parameterizing by $\mathsf{tw}$ or $\mathsf{td}$

Our objective in this section is to show that the meta-result of Gajarskỳ et al. [18] cannot be improved by replacing c-tdmod with $\mathsf{td}$, even when restricting ourselves to planar graphs of bounded maximum degree.

When proving lower bounds on the size of kernel for a parameter $\kappa$ such that $\kappa (\bigcup G_i) \le \text {poly}(\max (\kappa (G_i)))$ (such as $\mathsf{tw}$ or $\mathsf{td}$), compositions are generally simple, as taking the union of the input graphs preserves the parameter as required (which is obviously not true, for example, when parameterizing by the size of a solution). However, there is a problem occurring when proving that if the large union graph is a Yes-instance, then every (or there exists, depending if we are designing an and- or or-composition) instance is a Yes-instance, as the sizes of the solutions in the different $G_i$’s are not necessarily balanced. This explains why in [2] and in this work we introduce bounded versions of decision problems, where we already know that either a small solution exists, or there is no larger solution.

Let us now explain in detail how Bodlaender et al. [2] prove that several problems (including IS  and DS) do not admit a polynomial kernel parameterized by $\mathsf{tw}$ unless $\text {NP} \subseteq \text {coNP}/\text {poly}$. To that end, they first define a refinement problem, where the input of the classical problem is augmented with a witness I (corresponding to a subset of vertices or edges), and the question is to decide whether there exists a solution of size $|I|+1$ (or $|I|-1$ for a minimization problem). For example, in the IS-ref problem, given a graph G and an independent set I, the question is to decide whether G has an independent set of size $|I|+1$. Then, they show that

• 1. IS-ref is Karp NP-hard (by a Karp reduction from IS that simply adds $k-1$ independent vertices connected to all the old vertices),

• 2. IS-ref/$\mathsf{tw}$ is or-compositional,

• 3. IS-ref/$\mathsf{tw}$ does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ (which is a direct consequence of the two previous points using Theorem 1), and

• 4. IS/$\mathsf{tw}$ does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ (by simply observing that IS-ref/$\mathsf{tw}$$\le _{\textsc {ppt}}$IS/$\mathsf{tw}$ and using Theorem 3).

A drawback of this approach is that we lose planarity in Step 1. To obtain the same results for planar graphs, we propose the following modification of the previous approach, where we replace the positive witness by an upper bound (or a lower bound, for minimization problems), and use an and-composition instead.

In the following, $\varPi _{C}$ will denote any NP optimization graph problem where input graphs belong to a graph class $C$ and, and $\varPi ^{\text {dec}}_{C}$ its associated decision problem (given $G \in C$ and k, we have to decide whether $\mathsf{opt} (G) \ge k$ for a maximization problem, or $\mathsf{opt} (G) \le k$ for a minimization one).

Definition 6

(Decision problem with negative witness) Given a maximization (resp. minimization) problem $\varPi _{C}$, we define $\varPi _{C}^{\text {sup}}$ (resp $\varPi _{C}^{\text {inf}}$) as follows:

• Input: An instance (G, k) of $\varPi ^{\text {dec}}_{C}$ such that $\mathsf{opt} (G) \le k$ (resp. $\mathsf{opt} (G) \ge k$).

• Question: Decide whether $\mathsf{opt} (G)=k$.

Definition 7

We say that an optimization problem is additive if for every two graphs $G_1$ and $G_2$, $\mathsf{opt} (G_1 \cup G_2) = \mathsf{opt} (G_1)+\mathsf{opt} (G_2)$.

Observe that many classical optimization problems are additive, like IS or DS.

Proposition 2

Let $C$ be a graph class stable under disjoint union and let $\varPi _C$ be an additive optimization problem. Then $\varPi ^{\text {sup}}_C/\mathsf{td}$ and $\varPi ^{\text {inf}}_C/\mathsf{td}$ are and-compositional.

Proof

Let us only prove the result for $\varPi ^{\text {sup}}_C$, as the proof is similar for $\varPi ^{\text {inf}}_C$. Let t be an integer and let, for $i \le t$, $((G_i,k_i),\mathsf{td})$ be an instance of $\varPi _C^{\text {sup}}$, where $\mathsf{td}(G_i)=\mathsf{td}$. Let $G'$ be the disjoint union of the $G_i$’s and let $k'=\sum _{i=1}^t k_i$. We have $\mathsf{td}(G') \le \max (\mathsf{td}(G_i))$. As $C$ is stable under disjoint union, to verify that $(G',k')$ is an instance of $\varPi _C^{\text {sup}}$ it only remains to prove that $\mathsf{opt} (G') \le k'$. However, as $\varPi$ is additive, we have $\mathsf{opt} (G')=\sum _{1 \le i \le t} \mathsf{opt} (G_i) \le k'$.

It remains to verify that $\mathsf{opt} (G')=k' \Leftrightarrow \forall i, \mathsf{opt} (G_i)=k_i$. $\Leftarrow :$ is straightforward by the additivity of $\varPi$. $\Rightarrow :$ Let us suppose that $\sum _{1 \le i \le t} \mathsf{opt} (G_i)=k'$, and let $\ell \le t$. Again, as for every i we have $\mathsf{opt} (G_i) \le k_i$, we deduce $\mathsf{opt} (G_\ell ) \ge k_\ell$, and thus $\mathsf{opt} (G_\ell )=k_\ell$. $\square$

According to Theorem 1, we get the following results. Note that as $\varPi _C^{\text {sup}} \le _{\textsc {ppt}} \varPi ^{\text {dec}}_C$, we use Theorem 3 and also state the result for $\varPi ^{\text {dec}}_C$ in the next theorem.

Theorem 7

Let $C$ be a graph class stable under disjoint union.

• For any additive maximization problem $\varPi$ such that $\varPi _C^{\text {sup}}$ is Karp NP-hard, $\varPi ^{\text {sup}}_C/\mathsf{td}$ (and thus $\varPi ^{\text {dec}}_C/\mathsf{td}$) does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

• For any additive minimization problem $\varPi$ such that $\varPi _C^{\text {inf}}$ is Karp NP-hard, $\varPi ^{\text {inf}}_C/\mathsf{td}$ (and thus $\varPi ^{\text {dec}}_C/\mathsf{td}$) does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

According to the previous theorem, it turns out that to exclude a kernel by treedepth we only have to prove that the “negative witness” version of a decision problem is Karp NP-hard, which is usually almost already given by classical reductions.

Proposition 3

IS$^{\text {sup}}_{C}$ is Karp NP-hard, where $C$ is the class of planar graphs of maximum degree at most 4.

Proof

It is sufficient to observe that the reduction from planar 3-Sat(5) (where each variable appears in at most 5 clauses) to planar IS provided in [24] is in fact a reduction to planar IS$^{\text {sup}}$. For the sake of completeness let us recall this reduction.

An instance of planar 3-Sat(5) is described by a set C of m clauses $c_i$ and a set X of n variables $x_j$, where each $c_i$ contains exactly three literals (where a literal is of the form $x_j$ or $\bar{x}_j$). We can clearly assume that each variable appears both positively and negatively. Consider the incidence graph (which is planar) $G=(V,E)$ that has $V=C \cup X$ and has an edge from a variable to a clause if the variable or its negation appear in the clause. We define $G'$ by replacing each $c_i$ with a triangle $T_{c_i}$ (each vertex of the triangle is associated with a literal of the clause) and each $x_j$ with a cycle on 4 vertices $C_{x_j}=\{v^1_{x_j},v^1_{\bar{x}_j},v^2_{x_j},v^2_{\bar{x}_j}\}$ with edges $\{v^t_{x_j},v^{t'}_{\bar{x}_j} \mid t,t' \in \{1,2\}\}$. Then, we add edges between $T_{c_i}$ and $C_{x_j}$ in the following way. If $T_{c_i}$ contains a vertex v corresponding to $x_\ell$ (resp. $\bar{x}_\ell$), we add exactly one of the two edges $\{v,v^t_{\bar{x}_\ell }\}$ (resp. $\{v,v^t_{x_\ell }\}$) where $t \in \{1,2\}$, by choosing t such that $G'$ remains planar and of maximum degree 4. Indeed, as each variable appears in at most 5 clauses and appears both positively and negatively, it is always possible to embed the $C_{x_j}$’s such that the at most 5 edges of the form $\{v_1,v_2\}$ with $v_1$ in a clause triangle and $v_2 \in C_{x_j}$ do not cross when connecting to $C_{x_j}$, while avoiding to connect more than 2 edges to the same vertex in $C_{x_j}$.

Observe that $G'$ can be partitioned into m triangles and n$C_4$’s, implying $\alpha (G') \le m+2n$. As $\alpha (G')=m+2n$ if and only if the original instance of planar 3-Sat(5) is satisfiable, we get the desired result. $\square$

Note that it could be tempting to directly conclude that IS$^{\text {sup}}$ is NP-hard on planar graphs using the classical Turing reduction from IS on planar graphs (i.e., starting with an instance of IS$^{\text {sup}}$ with $k=n$, and decreasing k while the oracle for IS$^{\text {sup}}$ answers ‘No’). However, this would only prove that IS$^{\text {sup}}$ is Turing NP-hard on planar graphs, which is not sufficient to use Theorem 1 that requires Karp NP-hardness, even if this detail is generally not mentioned in the statement.

As IS is an additive problem, we immediately deduce the following corollary.

Corollary 1

IS / td does not admit a polynomial kernel on planar graphs of maximum degree at most 4 unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

To propagate the previous result to almost all problems covered by the meta-result of Gajarskỳ et al. [18], we will use Theorem 3 on folklore reductions and verify that the treedepth is polynomially preserved. To avoid tedious enumeration of problems, we restrict our attention to problems mentioned in Corollary 2 below. Note that for problems like Longest path and Treewidth where $\mathsf{opt} (G_1 \cup G_2) = \max (\mathsf{opt} (G_1),\mathsf{opt} (G_2))$, we also get that a polynomial kernel is unlikely to exist on planar graphs, as taking the union of input graphs provides a trivial or-composition.

Corollary 2

The following problems do not admit a polynomial kernel when parameterized by $\mathsf{td}$ or $\mathsf{tw}$ on planar graphs of bounded maximum degree unless $\text {NP} \subseteq \text {coNP}/\text {poly}$: VC, FVS, OCT, DS, r-DS, Chordal Vertex Deletion, Induced Matching.

Proof

We split the proof into several problems.

FVS, OCT, DS. For these three problems we use the same folkore reduction. Given an input (G, k) of VC, we define $G'$ by adding for each edge $\{u,v\}$ of G a vertex $x_{uv}$, and two edges $\{x_{uv},u\}$ and $\{x_{uv},v\}$. It is straightforward to verify that G admits a vertex cover of size at most k if and only if $G'$ admits a FVS (or OCT, or DS) of size at most k. As $\mathsf{td}(G') \le \mathsf{td}(G)+1$ (in the treedepth decomposition of G, for each vertex u in G we add degree of u new leaves attached to u), this is a PPT reduction.

Chordal vertex deletion. We use almost the same reduction as above: given an input (G, k) of VC, we define $G'$ by adding for each edge $\{u,v\}$ of G two vertices $x^1_{uv}$, $x^2_{uv}$, and edges $\{u,x^1_{uv}\},\{x^1_{uv},x^2_{uv}\}, \{x^2_{uv},v\}$.

r-DS. Given an input (G, k) of DS, we define $G'$ by adding a pendant $P_{r}$ attached to each vertex of G, and we set $k'=k$. As r is constant, the treedepth is polynomially preserved.

Induced Matching. Given an input (G, k) of IS, we define $G'$ by adding a pendant vertex to each vertex of G, and we set $k'=k$. $\square$

Note that Corollary 2 does not apply for $C^1$, defined as the class of connected planar graphs of bounded maximum degree, as $C^1$ is obviously not stable under disjoint union. However, there are two ways to get the same result for all problems of Corollary 2 for $C^1$, using the following observations.

If a problem $\varPi$ is solvable on planar graphs in time $\mathcal {O}^*(c^{\mathsf{td}})$ for some constant c (which is often the case [9, 12, 32]), we can show using an ad-hoc argument (i.e., depending on the problem) that $\varPi _{C}/$td$\le _{\textsc {ppt}} \varPi _{C^1}/$td. Let us illustrate this for IS. Given an instance (G, k) of IS$_{C}/\mathsf{td}$ having $k_1 \le k$ connected components $X_i$, let $v_i \in X_i$ be a vertex on the outer face of $X_i$. For every i we add two vertices $a_i,b_i$ and edges $\{a_i,b_i\}$, $\{b_i,v_i\}$ so that any optimal solution takes $a_i$ and not $b_i$, and we connect all the $b_i$’s by creating a path. We get a graph $G'$, and we set $k'=k+k_1$ so that (G, k) and $(G',k')$ are equivalent. $G'$ is still planar of bounded maximum degree and $\mathsf{td}(G') \le \mathsf{td}(G)\lceil \log _2(k_1+1) \rceil )$ (as $\mathsf{td}(P_{k_1}) \le \lceil \log _2(k_1+1) \rceil$). If $\log _2(k_1) \le \mathsf{td}(G)$ then this is PPT reduction. Otherwise, we can solve the original input in polynomial time and also get the reduction.

Alternatively, it is generally possible to directly cross-compose from $\varPi ^{\text {inf}}_{C^1}$ (or $\varPi ^{\text {sup}}_{C^1}$) to $\varPi _{C^1}/\mathsf{td}$ using again an ad-hoc argument to connect the graph. Given the t instances $\{G_i\}$ of $\varPi ^{\text {inf}}_{C^1}$, we define $G'$ by adding a dummy vertex $v_i$ on the outer face of $G_i$ and connecting the $v_i$’s by creating a path. If the dummy vertices are added such that $G'$ is a yes-instance if and only if all the $G_i$’s are yes-instances, we have an and-cross-composition, as again $\mathsf{td}(G') \le \max (\mathsf{td}(G_i))\lceil \log _2(k_1+1) \rceil )$, and this $\log$ factor is allowed in the parameter of a cross-composition.

6 Concluding Remarks and Further Research

In this article we studied the existence of polynomial kernels for problems parameterized by the size of a c-treedepth modulator, on graphs that are not necessarily sparse. On the positive side, we proved that Vertex Cover (or equivalently, Independent Set) parameterized by the size x of a c-treedepth modulator admits a polynomial kernel on general graphs with $x^{2^{\mathcal {O}(c^2)}}$ vertices, for every $c \ge 1$. A natural direction is to improve the size of this kernel. Since Vertex Cover parameterized by the distance to a disjoint collection of cliques of size at most c does not admit a kernel with $\mathcal {O}(x^{c-\epsilon })$ vertices unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [25], and since a clique of size c has treedepth c, the same lower bound applies to our parameterization; in particular, this rules out the existence of a uniform kernel. However, there is still a large gap between both bounds, hence there should be some room for improvement.

On the negative side, we proved that Dominating Set parameterized by the size of a c-treedepth modulator does not admit a polynomial kernel on 4-degenerate graphs for any $c \ge 2$. As Dominating Set with this parameterization admits a polynomial kernel on nowhere dense graphs [18], it follows that sparse graphs constitute the border for the existence of polynomial kernels for Dominating Set. This leads us to the following natural question: are there smaller parameters for which Dominating Set still admits polynomial kernels on sparse graphs? Since considering as parameter the treedepth of the input graph does not allow for polynomial kernels (see Sect. 5), we may consider as parameter the size x of a vertex set whose removal results in a graph of treedepth at most b(x), for a function b that is not necessarily constant. We prove in Appendix B that Dominating Set does not admit polynomial kernels on graphs of bounded expansion for $b(x) = \Omega (\log x)$, unless $\text {NP} \subseteq \text {coNP}/\text {poly}$. On the other hand, by combining the approach of Garnero et al. [20] to obtain explicit kernels via dynamic programming with the techniques of Gajarskỳ et al. [18] on graphs of bounded expansion, it can be shown—we omit the details here—that Dominating Set admits a polynomial kernel for $b(x) = \mathcal {O}(\log \log \log x)$ on graphs of bounded expansion whose expansion function f is not too “large”,² namely $f(d) = 2^{\mathcal {O}(d)}$. While this result is somehow anecdotal, we think that it may be the starting point for a systematic study of this topic.

We leave as an open question the existence of polynomial kernels on general graphs for other natural problems parameterized by the size of a treedepth modulator, such as Feedback Vertex Set (already studied by Jansen et al. [22] under several parameterizations) or Odd Cycle Transversal. In the spirit of the recent meta-kernelization results on sparse graphs [3, 16, 18, 20, 23], it would be interesting to find generic conditions for a problem to admit polynomial kernels on general graphs with this parameter. To the best of our knowledge, the only meta-kernelization results with structural parameters on general graphs are the work of Ganian et al. [19], where the parameter is the minimum number of parts $V_i$’s required in a vertex partition such that every $V_i$ is a module (for every $v \in V {\setminus } V_i$, either all or no vertex of $V_i$ is adjacent to v) and $G[V_i]$ has bounded rankwidth,³ and the further extension provided by Eiben et al. [14], which also subsumes the meta-kernelization framework of Gajarskỳ et al. [18].

Finally, it is worth studying whether the $2^c$-approximation algorithm of [18] for computing a c-treedepth modulator can be improved (maybe, using the algorithm of Reidl et al. [31] for computing treedepth), or whether a lower bound can be proved.

Appendices

List of Problems Considered in this Article

Stronger Negative Results for Dominating Set

In this section we rule out the existence of polynomial kernels for Dominating Set on graphs of bounded expansion for a parameter that is smaller than the size of a c-treedepth modulator. Let $b: \mathbb {N} \rightarrow R$ be a function. A b-treedepth modulator of a graph $G=(V,E)$ is a subset of vertices $X \subseteq V$ such that $\mathsf{td}(G[V{\setminus } X]) \le b(|X|)$, and we denote by b-$\mathsf{tdmod} (G)$ the size of a smallest b-treedepth modulator of G. Note that, in the particular case where the function b is constantly equal to a positive integer c, b-treedepth modulators correspond exactly to c-treedepth modulators. In the following proposition we show that $\textsc {DS}$ does not admit polynomial kernels on graphs of bounded expansion parameterized by the size of a b-treedepth modulator with $b(x) = \Omega (\log x)$.

Proposition 4

$\textsc {DS}/\log$-$\mathsf{tdmod}$ does not admit a polynomial kernel on graphs of bounded expansion unless $\text {NP} \subseteq \text {coNP}/\text {poly}$.

Proof

As in the proof of Proposition 1, it is sufficient to prove that $\textsc {RBDS}/U \le _{\textsc {ppt}} \textsc {DS} _{C_{BE}}/\log$-tdmod, as $\textsc {RBDS}/U$ (and even $\textsc {RBDS}/(k+U)$) does not admit a polynomial kernel unless $\text {NP} \subseteq \text {coNP}/\text {poly}$ [11]. Let $(G=(U,W,E),k)$ be an instance of $\textsc {RBDS}/U$ with $u=|U|$, $w=|W|$, and $m=|E|$. Let $G'=G^{3u\text {-sub}} \cup \tilde{G}$, where $\tilde{G}$ is a square grid on $(3u+1)^4$ vertices plus a vertex $\alpha$ connected to all vertices of this grid. G has a RB-dominating set of size k if and only if $G'$ has a dominating set of size $k+um+1$ (as we also have to take $\alpha$ in the solutions of $G'$). Let $X=U \cup \tilde{V}$ where $\tilde{V}$ is the vertex set of $\tilde{G}$. Note that $G'[V'{\setminus } X]$ is a disjoint collection of spiders $S_v$ (one rooted at each $v \in W$) of height $3u+1$. As $\mathsf{td}(S_v) \le 1+\mathsf{td}(P_{3u}) \le 2+ \log (3u+1) \le 2\log (3u+1) = \mathcal {O}(\log |X|)$ and $\mathsf{td}(G') \ge \mathsf{td}(\tilde{G}) \ge (3u+1)^2$, we get that X is a log-treedepth modulator of $G'$, and that $\log$-tdmod$(G') \le |X| \le \text {poly}(|U|)$. To summarize, we added a large grid to artificially increase the treedepth of $G'$. Moreover, observe that we could not reduce directly from DS/VC as before, as we need a lower bound depending on VC of the form $\frac{1}{\text {poly}(u)}$. Let us finally verify that $G'$ has bounded expansion. As $\tilde{G}$ is an apex graph, it has bounded expansion (as, for instance, planar graphs are well-known to have bounded expansion, and the addition of an apex vertex preserves this property), and thus it remains to verify that $G^{3u\text {-sub}}$ has bounded expansion. Let $K=K^{3u\text {-sub}}_{u,w}$. As $G^{3u\text {-sub}} \subseteq K$ as a subgraph, it is sufficient to prove that K verifies the condition of bounded expansion.

To that end, we will prove that $\tilde{\nabla }_r(K)\le r+2$, where $\tilde{\nabla }_r(G)$ denotes the density of a depth-r topological minor using the notation of [26]. Let H be a depth-r topological minor of K. If $r<3u$, then H is clearly 2-degenerate. If $r\ge 3u$, observe that every vertex of K that was originally in W has degree at most u, and every subdivision vertex (i.e., a vertex which is not already a vertex of $K_{u,w}$) has degree 2. As in a topological minor a vertex cannot have a higher degree than in the original graph, and K is bipartite, we conclude that H is u-degenerate. Hence, taking into account both cases, we have that $\tilde{\nabla }_r(K)\le r+2$. This proves that the class $\{K_{u,w}^{3u\text {-sub}} : u,w\in \mathbb {N}\}$ has bounded expansion. Thus, this is a PPT reduction and we get the desired result. $\square$