Boundaried Kernelization
Leonid Antipov, Stefan Kratsch · 2025
Read Boundaried Kernelization by Leonid Antipov, Stefan Kratsch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18476.txt.
Introduction
Leonid Antipov and Stefan Kratsch wrote this theoretical computer science paper, published in two thousand twenty-five, on shrinking hard problems before solving them. Kernelization is the art of trimming an input down to a small core with the same answer, but classic kernels demand a lot of global structure.
The authors propose boundaried kernelization, which trims local patches of a graph instead. The idea grows out of protrusion replacement, where a well-behaved lump of the input is swapped for a smaller stand-in. They show polynomial-size local kernels exist for a number of problems, and prove none can exist for others. The local tool also feeds back into the classic game: they use it to improve the kernel for Vertex Cover under a distance measure. The paper reframes preprocessing as a local craft.
Catalog record
| CREATOR | Leonid Antipov, Stefan Kratsch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18476
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Boundaried Kernelization Leonid Antipov, Stefan Kratsch Abstract The notion of a (polynomial) kernelization from parameterized complexity is a well-studied model for efficient preprocessing for hard computational problems. By now, it is quite well understood which parameterized problems do or (conditionally) do not admit a polynomial kernelization. Unfortunately, polynomial kernelizations seem to require strong restrictions on the global structure of inputs. To avoid this restriction, we propose a model for efficient local preprocessing that is aimed at local structure in inputs. Our notion, dubbed boundaried kernelization , is inspired by protrusions and protrusion replacement, which are tools in meta-kernelization [Bodlaender et al. J’ACM 2016]. Unlike previous work, we study the preprocessing of suitable boundaried graphs in their own right, in significantly more general settings, and aiming for polynomial rather than exponential bounds. We establish polynomial boundaried kernelizations for a number of problems, while unconditionally ruling out such results for others. We also show that boundaried kernelization can be a tool for regular kernelization by using it to obtain an improved kernelization for vertex cover parameterized by the vertex-deletion distance to a graph of bounded treedepth. 1 Introduction We introduce boundaried kernelization as a model for provably efficient local preprocessing , i.e., preprocessing that leverages local structure without having to explicitly consider the entire instance. This extends the notion of kernelization from parameterized complexity and is inspired by protrusions and protrusion replacement , which have been used, in particular, in meta theorems for kernelization (e.g., [ 6 ] ). Unlike protrusions, which are subgraphs of constant treewidth that have a constant-size interface/boundary to the rest of the graph, we study different kinds of internal structure and we allow for larger boundaries. Further, we usually aim to reduce the size to at most polynomial in boundary size and optional further parameters, while for protrusion replacement it is sufficient to reduce to a size with any (usually at least exponential) dependence on treewidth and boundary size. Let us first give some context. Parameterized complexity studies parameterized problems , which are classical problems augmented with one or more parameters such as solution size, dimension, or treewidth; often, parameters quantify structural properties. A central goal is to design algorithms that are fast when the chosen parameter value(s) are low, showing that the corresponding property or structure is algorithmically beneficial (called fixed-parameter tractable algorithms). This parameterized setting also allows for a robust notion of efficient preprocessing: A kernelization for a parameterized problem is an efficient algorithm that expects an instance (x,k) , with parameter k , and returns an equivalent instance (x^{\prime},k^{\prime}) of size upper bounded by some computable function f(k) . In particular, one is interested what parameterized problems admit polynomial kernelizations where the function f is polynomially bounded. Kernelization has been intensely studied (see, e.g., recent works [ 4 , 5 , 11 , 19 , 24 , 25 , 36 , 38 , 39 , 43 , 44 , 47 ] or the dedicated book [ 28 ] ) and, by now, it is quite well understood which problems do or (conditionally) do not admit polynomial kernelizations. Moreover, there are both meta results (e.g., [ 6 , 27 , 29 , 45 ] ), giving upper bounds for whole classes of problems, as well as dichotomy results (e.g., [ 41 , 40 , 18 , 11 ] ), classifying all problems in some class into admitting or (conditionally) not admitting a polynomial kernelization. We see two main motivations for studying local preprocessing: First , kernelizations usually rely on reduction rules , which usually apply to local configurations in the input. For example, this includes simple rules like folding of degree-two vertices for vertex cover [ 14 ] and seeking flowers , i.e., cycles that pairwise intersect in the same vertex, for feedback vertex set [ 10 , 46 ] . In other words, depending on the kind of reduction rule, the scope of the rule may vary, but beyond the required scope it usually does not matter what else is present in the instance. 1 1 1 A notably different case: Kernelizations obtained via cut-covering sets and other matroid-based techniques [ 42 ] use the entire instance to discover safe reduction steps. Is there a sensible way of capturing local structure and giving local guarantees for the effectiveness of preprocessing? Second , most polynomial kernelizations in the literature are for parameterization by solution size or by the distance to some tractable special case for the problem. E.g., we are given a graph G and a modulator X\subseteq V(G) such that G-X belongs to a graph class where the target problem can be solved efficiently, with |X| being the parameter. Intuitively, unless \mathsf{P}=\mathsf{NP} , efficient preprocessing can at best deal with tractable parts so the parameter must directly or indirectly allow to (at least) bound the size of the remainder of the instance, which may be structured arbitrarily. Together, this yields a fairly strict requirement for kernelization to be useful: Almost the entire instance must match some tractable special case for the problem in question. What if only parts of an instance fulfill such a restriction? Do we still get nontrivial guarantees for efficient preprocessing? Our work. Inspired by protrusions and protrusion replacement from meta kernelization [ 6 ] , we use boundaried graphs to define boundaried kernelization (see Section 3 for formal definitions): A boundaried graph G_{B} is a graph G with the additional specification of a set B\subseteq V(G) of boundary vertices. Informally, a boundaried kernelization for, e.g., the problem vertex cover [fvs], i.e., vertex cover parameterized by the size of a given feedback vertex set, is a polynomial-time algorithm that expects as input a boundaried graph G_{B} with forest-modulator X of size k , and returns a boundaried graph G^{\prime}_{B} of size bounded by a function of parameter k and boundary size |B| such that attaching the same graph H_{B} to either G_{B} or G^{\prime}_{B} (by identification of boundary vertices, also called gluing ) will yield graphs that are equivalent with respect to vertex cover . In this way, local preprocessing for vertex cover with respect to local structure as quantified by modulator X corresponds to a boundaried kernelization for vertex cover [fvs]. Note that for B=\emptyset and gluing the empty graph to G_{B} this includes the requirement that G and G^{\prime} are equivalent for vertex cover (and G^{\prime} is of size bounded by a function of k ), which essentially constitutes a regular kernelization for vertex cover [fvs] (cf. Lemma 4 ). Accordingly, we mainly work with problems that admit a polynomial kernelization. We establish polynomial size boundaried kernelizations for several problems that are known to admit regular polynomial kernelizations. This confirms the intuition that the local nature of reduction rules often allows us to work on the well-structured part only and ignore the rest of the instance. Theorem 1 . The following parameterized problems admit a polynomial boundaried kernelization: vertex cover [vc] , vertex cover [fvs] , feedback vertex set [fvs] , long cycle [vc] , long path [vc] , and hamiltonian cycle [vc] , hamiltonian path [vc] as well as hamiltonian cycle/path [ \#v,\text{deg}(v)\neq 2 ] . We complement this by proving unconditionally that some problems do not admit