Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
Till Fluschnik · DepositOnce · 2020
Preprocessing and data reduction are basic algorithmic tools. In parameterized algorithmics, such preprocessing is defined by (problem) kernelization, where an equivalent instance (the kernel) is computed in polynomial time and its size can be upper-bounded only in a function of the parameter value of the input instance. In this thesis, we study lower and upper bounds on kernelization regarding polynomial-sized kernels as well as variants of kernelization like kernelization for polynomial-time solvable problems. We introduce a new family of fractal-like graphs that we call T-fractals. Using these T-fractals in a common machinery for proving kernelization lower bounds, we refute (under some complexity-theoretic assumptions) the existence of polynomial kernels for some distance-related cut problems. One of these problems is the Length-Bounded Edge-Cut problem, for which the status of polynomial kernelization remained unknown for some time. We underline and extend the usage of the so-called diminisher framework for excluding restrictive kernels of polynomial size under the assumption of P being different to NP. We prove that the original framework applies to more parameterized problems than previously known. In order to exclude less restrictive kernels of polynomial size, we extend the framework. We prove, however, that this extended framework does not apply to several parameterized problems. Yet, we prove that the framework applies to polynomial-time solvable problems, yielding first direct kernelization lower bounds in this class of problems. In addition, we prove a kernelization dichotomy regarding the running time and the size of the kernel for the polynomial-time solvable problem of computing the hyperbolicity of a graph. Finally, we study classic graph problems under the so-called secluded concept, where constraints on the neighborhood of the subgraph in question are present. One of our problems is a secluded variant of the classic problem of finding a short path connecting two terminal vertices. For this problem, we prove a hierarchy of polynomial kernelizations regarding several structural graph parameters. Herein, we obtain polynomial kernels via the so-called “losing weight” technique. We outline this technique and prove that it applies to more problems than previously known. Eventually, we study two more problems in the secluded setup and prove how different constraints on the neighborhood lead to different complexity-theoretic classifications not only regarding polynomial kernelizability.