1 Introduction↩︎

For a fixed graph \(H\), the following \(H\)-Packing problem [1], [2] is a fundamental problem in theoretical computer science, extensively studied in the literature on parameterized algorithms [3]–[7].

\(H\)-Packing:

Input: An undirected graph \(G\) and an integer \(k\in \mathbb{Z}_{\geq 0}\).

Question: Does \(G\) contain \(k\) vertex-disjoint (not necessarily induced) subgraphs isomorphic to \(H\)?

One of the lines of research for this problem is kernelization, which refers to a polynomial-time algorithm that transforms an instance into a possibly smaller equivalent instance. For general \(H\), the standard upper bounds come from reducing \(H\)-Packing to \(d\)-Set Packing:

\(d\)-Set Packing:

Input: Universe \(U\), set family \(\mathcal{F}\subseteq \binom{U}{d}\), and integer \(k\in \mathbb{Z}_{\geq 0}\).

Question: Does \(\mathcal{F}\) contain \(k\) pairwise disjoint sets?

Fellows et al. [4] provided a kernel of \(O(k^d)\) sets for this problem, while Abu-Khzam [8] gave a kernel with \(O(k^{d-1})\) elements and \(O(k^d)\) sets. By reducing \(H\)-Packing to \(d\)-Set Packing in the standard way and then kernelizing the resulting Set Packing instance, one obtains an upper bound of \(O(k^{|V(H)|-1})\) vertices and \(O(k^{|V(H)|})\) edges for \(H\)-Packing. Indeed, one may lift the Set Packing kernel back to an \(H\)-Packing instance by keeping the vertices and edges that appear in the surviving copies of \(H\). For connected \(H\), the vertex bound \(O(k^{|V(H)|-1})\) was obtained earlier by Moser [7]. This leads to the following question:

Can one beat the \(d\)-Set Packing kernel bound for \(H\)-Packing?

Known positive answers were confined to a few patterns. Star packing, that is, \(K_{1,d}\)-Packing, has been studied in the kernelization literature. Prieto-Rodriguez and Sloper [9] obtained an \(O(k^2)\)-vertex kernel for general \(K_{1,d}\)-Packing, and this was improved to a \(O(k)\)-vertex kernel [10], [11]. The special case \(P_3\) has attracted attention: Prieto-Rodriguez and Sloper [9] obtained a \(15k\)-vertex kernel, and later work improved this to the best bound of \(5k\) vertices [12]–[14]. Dell and Marx [3] showed that when \(H\) is a path on \(\ell\) vertices, one can beat the general bound with kernels of \(O(k^{2.5})\) edges for \(\ell=4\) and \(O(k^3)\) edges for \(\ell\geq 5\). Cervený, Choudhary, and Suchý [15] studied the hitting counterpart, obtaining kernels of \(O(k^2)\) edges for \(\ell=4,5\) and \(O(k^4)\) edges for general \(\ell\).¹ However, beyond these examples, the list of graphs \(H\) known to beat the \(d\)-Set Packing bound remained very short.

This paper gives several new affirmative answers. At the same time, it shows that the picture is subtler than expected. Concretely, we show that deleting a single vertex from the pattern may lead to provably worse kernelization behavior. This is surprising, and suggests that a more systematic understanding of kernelization for \(H\)-Packing is still needed.

Our main focus is the subdivided star \(S_{d_1,d_2}\), which has \(d_1\) branches of length \(1\) and \(d_2\) branches of length \(2\) (1). In particular, \(S_{1,1}=P_4\) (\(4\)-vertex path), \(S_{0,2}=P_5\) (\(5\)-vertex path), and \(S_{d,0}=K_{1,d}\) (\(d\)-leaf star). For the case \(d_2=0\) (that is, stars), linear-vertex kernels are already known [10], [11].

Our first theorem extends this line beyond stars, giving quadratic-vertex and cubic-edge kernels when \(d_2=1\) and in the two additional cases \((d_1,d_2)\in\{(0,2),(1,2)\}\).

For the family \(H=S_{d_1,1}\), the hidden constants depend polynomially on \(d_1\).

At a high level, the argument has two steps, both using reductions based on the expansion lemma: first, one finds a small set that captures the non-trivial part of the graph, and then one reduces the remaining independent side.

The cleanest case is \(P_5=S_{0,2}\). The key step is to obtain a vertex cover of size \(O(k)\). Let \(C\) be the union of vertex sets of a maximal family of vertex-disjoint copies of \(P_5\); then \(|C|=O(k)\), and \(C\) meets every copy of \(P_5\) by maximality. A reduction based on the expansion lemma reduces the number of non-trivial components of \(G-C\) to \(O(k)\). We then obtain a linear-size vertex cover, because every connected \(P_5\)-free graph has a constant-size vertex cover. Thus each non-trivial component of \(G-C\) contributes only constantly many cover vertices, while all remaining vertices are isolated in \(G-C\). Consequently the resulting graph has a vertex cover of size \(O(k)\).

The second step is to reduce the remaining independent side by keeping only a bounded number of vertices for each relevant subset of the vertex cover. For \(P_5\), applying this to the linear-size vertex cover obtained in the first step yields a quadratic-vertex kernel.

For \(S_{1,2}\) and \(S_{d_1,1}\), the same first idea starts the proof, but the vertex-cover argument used for \(P_5\) is too rigid. To handle this, we introduce the notion of an isolating set. Concretely, we seek an isolating set \(C\) for which \(V(G)\) admits a partition \(V(G)=C\uplus Z\uplus I\), where \(I\) is independent and there is no edge between \(I\) and \(Z\). When \(Z=\emptyset\), this set \(C\) is exactly a vertex cover. Here one again applies reduction based on the expansion lemma to obtain \(|C|=O(k)\), but now keeps an additional set \(Z\) of size \(O(k^2)\) that contains the non-trivial surviving part, leaving the rest in the independent set \(I\). The second step then reduces this \(I\)-side exactly as in the \(P_5\) case. This yields [thm:short-subdivided-stars].

We next turn to arbitrary subdivided stars with \(d_1 \ge 1\).

The kernelization landscape for subdivided stars is summarized in 2.

The overall strategy again has two steps. First, we reduce the instance to one with a vertex cover of size \(O(k^2)\). Unlike the cases covered by [thm:short-subdivided-stars], this vertex cover is no longer linear in \(k\). Starting from a maximal packing, we take a maximal matching in the remaining graph. Because the vertices outside this matching form an independent set, the packing vertices together with the matched vertices already form a vertex cover. The key point is then to show, by a degree analysis around the matching, that after deleting vertices that belong to no copy of \(H\), only \(O(k^2)\) matched vertices need to be kept. Second, we reduce the remaining part outside this vertex cover using the same general approach as in the proof of [thm:short-subdivided-stars].

The assumption \(d_1\ge 1\) in [thm:general-result] is essential for the second step. We introduce the notion of the pattern’s \(r\)-replaceability, defined formally in 3. Roughly speaking, this notion controls how efficiently the part outside the vertex cover or isolating set can be represented once a partition \(V(G)=C\uplus Z\uplus I\) is given. Our general reduction theorem shows that, from such a partition, one obtains a kernel with \(O(|C|^r+|Z|)\) vertices (1).

For subdivided stars, the distinction between the cases \(d_1=0\) and \(d_1\ge 1\) turns out to be fundamental. If \(d_1\ge 1\), then the presence of a branch of length \(1\) makes it possible to replace the part of a copy outside the cover while preserving the pattern, and \(S_{d_1,d_2}\) is already \(2\)-replaceable, which is what ultimately yields the polynomial kernel of [thm:general-result]. In contrast, when \(d_1=0\), our framework gives only \(d_2\)-replaceability for \(S_{0,d_2}\). One might suspect that this is merely a limitation of our method. The next theorem, however, shows that it reflects a genuine structural barrier:

This shows that deleting a single vertex from the pattern can make kernelization strictly harder: \(S_{1,7}\)-Packing admits a kernel with \(O(k^6)\) edges by [thm:general-result], whereas \(S_{0,7}\)-Packing does not admit a compression of size \(O(k^{7-\epsilon})\) unless \(\textrm{NP}\subseteq \textrm{coNP}/\textrm{poly}\). It also highlights the role of replaceability: \(S_{1,7}\) is already \(2\)-replaceable, while \(S_{0,7}\) is only \(7\)-replaceable, and this gap is reflected in their kernelization complexity.

Finally, we consider the paw ([fig:paw]), i.e., a triangle with a pendant edge.

This is the first example, to the best of our knowledge, of beating the general \(d\)-Set Packing bound for a pattern that contains a cycle. The proof again follows a two-step kernelization scheme, but now in a form adapted to triangles. Starting from a maximal paw packing, one reduces the number of triangle components outside the initial set and controls large matchings around its vertices. This yields an equivalent instance with a vertex cover \(C\) of size \(O(k^2)\). The remaining outside vertices matter only through \(O(k^2)\) edges of \(C\) that can participate in triangles, and a second matching-based kernelization using these edges gives the kernel in [thm:paw-result].

The algorithmic study of \(H\)-Packing goes back to Hell and Kirkpatrick’s work on generalized matching problems [1], [16]: for fixed \(H\), the problem is polynomial-time solvable when each connected component of \(H\) has at most two vertices and NP-hard when \(H\) has at least three vertices. For broader background on the algorithmic and computational aspects of graph packing, we refer to Yuster’s survey [2].

From the parameterized perspective, the generic benchmark is \(d\)-Set Packing. For that problem, the fastest known generic randomized algorithms are due to Björklund, Husfeldt, Kaski, and Koivisto [17]; in particular, they solve \(3\)-Set Packing in time \(O^*(3.328^{k})\) and \(4\)-Set Packing in time \(O^*(7.312^k)\).² Deterministically, Nederlof [18] very recently obtained an \(O^*(2^{dk+o(dk)})\)-time algorithm for \(d\)-Set Packing. Via the standard reduction from \(H\)-Packing to \(d\)-Set Packing, this yields fixed-parameter algorithms for \(H\)-Packing. For the special case \(P_3\), Zehavi [19] gave a deterministic algorithm with running time \(O^*(6.75^k)\) based on Feng et al. [20].

Concerning kernelization, generic kernels for \(H\)-Packing with \(O\!\left(k^{|V(H)|-1}\right)\) vertices and \(O(k^{|V(H)|})\) edges follow from \(d\)-Set Packing [4], [8]. For connected \(H\), Moser [7] had earlier obtained the vertex bound \(O\!\left(k^{|V(H)|-1}\right)\) directly for \(H\)-Packing. On the lower-bound side, Dell and Marx [3] showed that \(H\)-Packing does not admit a kernel of \(O(k^{2-\epsilon})\) edges for any \(\epsilon>0\) and any connected graph \(H\) with at least three vertices unless \(\textrm{NP}\subseteq \textrm{coNP}/\textrm{poly}\). For cliques, they further proved that \(K_d\)-Packing does not admit a kernel of \(O(k^{d-1-\epsilon})\) edges for any \(\epsilon>0\) and any \(d\ge 3\) unless \(\textrm{coNP}\subseteq \textrm{NP}/\textrm{poly}\).

Before the present paper, the only graphs known to beat these generic upper bounds were essentially stars and paths. For stars, the kernel size was improved from quadratic to linear [9]–[11]; for the special case \(P_3\), the kernel size was later reduced further to \(5k\) vertices [9], [12]–[14]. For paths, Dell and Marx [3] obtained kernels with \(O(k^{2.5})\) edges for \(P_4\) and \(O(k^3)\) edges for \(P_\ell\) with \(\ell\geq 5\).

A variant that considers packing induced subgraphs instead of subgraphs, Induced \(H\)-Packing, has also been studied. Via the standard reduction to Set Packing, one obtains a compression with \(O(k^{|V(H)|-1})\) elements and \(O(k^{|V(H)|})\) sets. Fomin et al. [21] obtained an \(O(k^{5/3})\)-vertex kernel for induced \(P_3\)-Packing via expansion lemma, and Bessy et al. [22] improved this to \(O(k)\) vertices via rainbow matching. These papers also obtained improved kernels for packing oriented triangles in tournaments.

2 Preliminaries↩︎

We assume that the reader is familiar with the basic notions of parameterized complexity; for background, we refer to Cygan et al. [23].

Graphs.

In this paper, all graphs are finite, simple, and undirected. For a graph \(G\) and a vertex set \(X\subseteq V(G)\), we write \(G[X]\) for the induced subgraph on \(X\) and \(N_G(X)\) for the neighborhood of \(X\) in \(G\); if \(X=\{x\}\), we abbreviate \(N_G(\{x\})\) to \(N_G(x)\). For two disjoint vertex sets \(X,Y\subseteq V(G)\), we write \(G[X,Y]\) for the bipartite graph obtained from \(G[X\cup Y]\) by removing all edges in \(G[X]\) and \(G[Y]\). We denote a path by the sequence of its vertices, so \((v_1,\dots,v_r)\) is the path with edges \(v_iv_{i+1}\) for \(i\in\{1,\dots,r-1\}\). For \(D\subseteq V(G)\) and \(X\subseteq V(G)\), let \(N_D(X):=N_G(X)\cap D\), and for an integer \(r\ge 1\), let \(N_D^{\le r}(X)\) denote the set of vertices \(v\in D\) such that, for some \(x\in X\), there is a path \((x,\dots,v)\) of length at most \(r\), or equivalently, at most \(r\) edges, whose internal vertices all lie in \(D\).

We write \(\deg_G(v)\) for the degree of a vertex \(v\) in \(G\), \(\Delta(G)\) for the maximum degree of \(G\), \(\operatorname{dist}_G(u,v)\) for the distance between \(u\) and \(v\) in \(G\), and \(\operatorname{diam}(G)\) for the diameter of a connected graph \(G\). In particular, every subdivided star \(S_{d_1,d_2}\) has diameter at most \(4\).

Kernelization.

Two instances \((G,k)\) and \((G',k')\) of \(H\)-Packing are equivalent if either both are yes-instances or both are no-instances. A kernelization of size \(f(k)\) for a parameterized problem is a polynomial-time algorithm that maps each instance \((x,k)\) to an equivalent instance \((x',k')\) of the same problem whose size is bounded by a computable function \(f(k)\). More generally, a compression of size \(f(k)\) outputs an equivalent instance of some parameterized problem that can be encoded using \(O(f(k))\) bits. In this paper, for graph problems we measure the size of a reduced instance in terms of the number of vertices and edges of the reduced graph. A reduction rule that replaces an instance \((G,k)\) by an instance \((G',k')\) is safe if \((G,k)\) and \((G',k')\) are equivalent.

For a fixed graph \(H\), we will repeatedly use the following elementary reduction rule.

After exhausting the rule, we may assume that every vertex and every edge of \(G\) belongs to a copy of \(H\). Since \(H\) is fixed, applicability of the rule can be checked in polynomial time.

2.0.0.0.1 Expansion lemma.

The expansion lemma, originally introduced by Thomassé [24] in his quadratic-kernel algorithm for Feedback Vertex Set, is a standard tool in kernelization. For background and applications, we refer to the textbook on kernelization by Fomin et al. [25]. In this paper, we repeatedly use the following formulation due to Fomin et al. [21].

Fix \(H=S_{d_1,d_2}\) among these three graphs and write \(d:=d_1+d_2\). We begin by computing a maximal family \(\mathcal{P}\) of pairwise vertex-disjoint copies of \(H\) and setting \(C:=\bigcup_{P\in\mathcal{P}}V(P).\) This can be done in polynomial time. If \(|\mathcal{P}|\ge k\), then \((G,k)\) is a yes-instance. Hence we may assume that \(|\mathcal{P}|<k\). It follows that \(|C|=|V(H)|\cdot |\mathcal{P}|<|V(H)|k\le (2d+1)k\), and maximality implies that \(G-C\) is \(H\)-free.

2.1 Non-trivial component reduction↩︎

Let \(\mathcal{R}\) be the set of connected components of \(G-C\) with at least two vertices, and let \(J\) be the set of isolated vertices of \(G-C\). Then \(V(G)\setminus C = J \uplus \bigl(\biguplus_{R\in\mathcal{R}}V(R)\bigr).\)

Define a graph \(\Gamma:=(C\uplus \mathcal{R},F)\) by joining \(c\in C\) and \(R\in\mathcal{R}\) whenever \(c\) has a neighbor in \(R\) in the graph \(G\). Applying 2 to \(\Gamma\) with \(q=d\), we obtain subsets \(\widehat C\subseteq C\) and \(\widehat{\mathcal{R}}\subseteq \mathcal{R}\), define \(A:=C\setminus \widehat C\) and \(\mathcal{D}:=\mathcal{R}\setminus \widehat{\mathcal{R}}\), and obtain an edge set \(M\subseteq F\) such that

1. \(|\widehat{\mathcal{R}}|\le d|\widehat C|\),

2. every vertex of \(A\) is incident in \(M\) with exactly \(d\) edges,

3. every vertex of \(\mathcal{D}\) is incident in \(M\) with at most one edge,

4. there is no edge of \(\Gamma\) between \(\widehat C\) and \(\mathcal{D}\).

We say that a component \(R\in\mathcal{D}\) is assigned to a vertex \(c\in A\) if \(cR\in M\). Then the second property implies that exactly \(d\) components of \(\mathcal{D}\) are assigned to each vertex of \(A\), while the third property implies that each component of \(\mathcal{D}\) is assigned to at most one vertex of \(A\).

We apply the following reduction rule.

Let \((G',k')\) be the instance obtained by applying 2. Replace the current instance by \((G',k')\), and rename \(\widehat C\) and \(\widehat{\mathcal{R}}\) as \(C\) and \(\mathcal{R}\). Then \(|\mathcal{R}|\le d|C|<d|V(H)|k\). Moreover, if a component \(R\in\mathcal{R}\) has no neighbor in \(C\), then no copy of \(H\) can use a vertex of \(R\): indeed, \(R\subseteq G-C\) is \(H\)-free and has no edge to the rest of the graph outside \(R\). Hence all such components may be deleted.

2.2 Reduction for \(P_5\)↩︎

For \(H=P_5\), 2 already leaves only \(O(k)\) non-trivial components outside \(C\). The key point is that each such component has a vertex cover of constant size.

2.3 Reduction for \(S_{1,2}\)↩︎

For \(H=S_{1,2}\), we again seek an equivalent instance together with an isolating set \(C\) and a partition \(V(G)=C\uplus Z\uplus I\) witnessing this, where \(|C|=O(k)\) and \(|Z|=O(k^2)\).

We now return to the instance produced by 2 with \(H=S_{1,2}\). If that reduction certifies a yes-instance, we return the disjoint union of \(k\) copies of \(S_{1,2}\). Otherwise, we have \(|C|<6k\) and \(|\mathcal{R}|<18k\).

For each component \(R\in \mathcal{R}\), move every vertex of degree at least \(3\) in \(R\) to \(C\). By 6, this adds at most \(6|\mathcal{R}|=O(k)\) vertices, so still \(|C|=O(k)\). Let \(D\) be the union of all non-trivial components of \(G-C\). Then \(\Delta(D)\le 2\). Moreover, by 1, every vertex of \(D\) belongs to some copy of \(S_{1,2}\). Since each such copy intersects \(C\) and \(\operatorname{diam}(S_{1,2})=4\), it follows that \(V(D)\subseteq N_D^{\le 4}(C).\)

A vertex subset \(X\subseteq D\) is scattered if for any \(x,y\in X\), \(\operatorname{dist}(x,y)\geq 3\) within \(D\). We apply the following reduction rule:

While computing a maximum scattered set in \(N_D(c)\) is hard in general, for each \(c\in C\) we greedily construct a maximal scattered set \(X_c\subseteq N_D(c)\), and apply 3 only when \(|X_c|\ge 5k\). Once this process stops, every \(c\in C\) satisfies \(|X_c|<5k\).

3 Kernelization from an Isolating Set↩︎

The goal of this section is to reduce instances of \(H\)-Packing given together with an isolating set to instances of a bounded number of vertices, thereby completing the kernelization.

3.1 General reduction↩︎

Here, we give an algorithm that kernelizes the given instance \((G,k)\) with an isolating set \(C\). We work with the general \(H\); we begin by defining the following \(r\)-replaceability, which is a condition that depends solely on the graph \(H\).

The goal here is to prove the following.

Let \((G,k)\) be an instance of \(H\)-Packing with a partition \(V(G)=C\uplus I\uplus Z\), which witnesses that \(C\) is an isolating set. Let \[L:=\biguplus_{i=1}^r \bigl(\tbinom{C}{i}\times [x_i]\bigr),\] where \([x]=\{1,\dots,x\}\). For a vertex \(\lambda=(D,j)\in \tbinom{C}{i}\times [x_i]\), write \(D(\lambda):=D\). Define the bipartite graph \(\mathcal{B}=(L\uplus I,F)\) by letting \(\lambda v\in F\) if and only if \(D(\lambda)\subseteq N_G(v)\).

Apply 2 to \(\mathcal{B}\) with \(q=1\). We obtain subsets \(\widehat L\subseteq L\), \(\widehat I\subseteq I\), and an edge set \(M\subseteq F\) such that:

1. \(|\widehat I|\le |\widehat L|\),

2. every vertex of \(L\setminus \widehat L\) is incident with exactly one edge of \(M\),

3. every vertex of \(I\setminus \widehat I\) is incident with at most one edge of \(M\),

4. there is no edge of \(\mathcal{B}\) between \(\widehat L\) and \(I\setminus \widehat I\).

For every \(\lambda\in L\setminus \widehat L\), let \(m_\lambda\in I\setminus \widehat I\) be the unique vertex satisfying \(\lambda m_\lambda\in M\). For every \(D\in \bigcup_{i=1}^r \tbinom{C}{i}\), define \[R_D:=\{m_\lambda : \lambda\in L\setminus \widehat L\text{ and }D(\lambda)=D\}.\] Thus \(R_D\) is the set of such vertices \(m_\lambda\) whose left endpoint \(\lambda\) satisfies \(D(\lambda)=D\). Let \(R:=\bigcup_{D\in \bigcup_{i=1}^r \tbinom{C}{i}} R_D\). We apply the following rule.

Now we prove that the reduction is safe. Since \(G'\subseteq G\), it is clear that if \((G',k)\) is a yes-instance, then \((G,k)\) is also a yes-instance. Thus, it remains to prove the converse. The idea is to show that each copy \(P\) in a packing of \(G\) can be replaced by a copy contained in a set \(\mathsf{Ext}(P)\subseteq V(G')\) (12), defined later, and that these sets are pairwise disjoint for different copies (11). Fix a packing \(\mathcal{P}\) of \(k\) copies of \(H\) in \(G\). For each \(P\in \mathcal{P}\), define \[\mathsf{Ext}(P):=(V(P)\cap (C\cup Z\cup \widehat{I}))\cup \bigcup_{D\in \bigcup_{i=1}^{r}\binom{V(P)\cap C}{i}}R_D.\]

3.2 Replaceability Analysis↩︎

In this subsection, we state that \(P_5\) and \(S_{d_1,d_2}\) with \(d_1\ge 1\) are \(2\)-replaceable, whereas \(S_{0,d}\) is not \(\ell\)-replaceable for any \(\ell<d\). We begin with \(P_5\).

We extend this to all subdivided stars with at least one branch of length \(1\). The presence of such a branch is what makes this case \(2\)-replaceable.

We now turn to the line \(d_1=0\) and show that this phenomenon disappears. In that case the replaceability parameter cannot be pushed below \(d\).

This argument does not extend to the case \(d_1=0\). The first step, namely 9, still applies and reduces \(S_{0,d_2}\)-Packing to an equivalent instance with a vertex cover of size \(O(k^2)\). However, the second step no longer improves the generic bound: by [prop:S0d-not-replaceable], the graph \(S_{0,d_2}\) is not \(\ell\)-replaceable for any \(\ell<d_2\), so 1 yields at best an \(O(k^{2d_2})\)-vertex kernel, which is no better than the generic \(d\)-Set Packing bound.

4 Conclusion↩︎

In this paper, we obtained kernels for \(H\)-Packing beating the generic \(d\)-Set Packing bound for several new pattern graphs \(H\). In particular, we proved:

• for \(H=P_5\) and \(H=S_{1,2}\), a kernel with \(O(k^2)\) vertices and \(O(k^3)\) edges,

• for \(H=S_{d_1,1}\), a kernel with \(O(k^2)\) vertices and \(O(k^3)\) edges,

• for \(H=S_{d_1,d_2}\) with \(d_1\ge 1\), a kernel with \(O(k^4)\) vertices and \(O(k^6)\) edges, and

• for the paw, a kernel with \(O(k^2)\) vertices and \(O(k^4)\) edges.

By contrast, we did not obtain a smaller kernel for the line \(H=S_{0,d}\). Instead, we proved that for every \(d\ge 3\) and every \(\varepsilon>0\), \(S_{0,d}\)-Packing does not admit a compression of size \(O(k^{d-\varepsilon})\) unless \(\textrm{NP}\subseteq \textrm{coNP}/\textrm{poly}\). In particular, this shows that kernelization for \(H\)-Packing is not monotone under taking induced subgraphs. This suggests that the kernel complexity of \(H\)-Packing is rather subtle, and that further investigation is needed.

References↩︎

---

1. These kernel bounds for the hitting counterpart do not seem to imply analogous bounds for the packing problem; this was also confirmed to us by Ondřej Suchý (private communication). Intuitively, preserving a small hitting set appears substantially easier than preserving many pairwise disjoint copies.↩︎

2. The \(O^*\) notation suppresses polynomial factors.↩︎