Stefan Kratsch

A kernelization is an efficient algorithm that given an instance of a parameterized problem returns an equivalent instance of size bounded by some function of the input parameter value. It is quite well understood which problems do or (conditionally) do not admit a kernelization where this size bound is polynomial, a so-called polynomial kernelization. Unfortunately, such polynomial kernelizations are known only in fairly restrictive settings where a small parameter value corresponds to a strong restriction on the global structure on the instance. Motivated by this, Antipov and Kratsch [WG 2025] proposed a local variant of kernelization, called boundaried kernelization, that requires only local structure to achieve a local improvement of the instance, which is in the spirit of protrusion replacement used in meta-kernelization [Bodlaender et al.\ JACM 2016]. They obtain polynomial boundaried kernelizations as well as (unconditional) lower bounds for several well-studied problems in kernelization. In this work, we leverage the matroid-based techniques of Kratsch and Wahlström [JACM 2020] to obtain randomized polynomial boundaried kernelizations for \smultiwaycut, \dtmultiwaycut, \oddcycletransversal, and \vertexcoveroct, for which randomized polynomial kernelizations in the usual sense were known before. A priori, these techniques rely on the global connectivity of the graph to identify reducible (irrelevant) vertices. Nevertheless, the separation of the local part by its boundary turns out to be sufficient for a local application of these methods.

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.

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G , two vertices s, t ∈ V(G) , and an integer k , adds (randomly) to G a number of arcs such that for every minimal st -cut Z in G of size at most k , with probability 2 ^{−poly( k )} the set Z becomes a minimum st -cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: Chain SAT , defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], a number of weighted variants of classic directed cut problems, such as Weighted st - Cut or Weighted Directed Feedback Vertex Set . By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H , if the List H - Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.