Parameterized Tractability Landscape of Partitioning, Covering, and Satisfiability Problems [HBNI Th 283]

Abstract

This thesis investigates the parameterized complexity of NP-hard partitioning, cov- ering, and satisfiability problems, identifying tractable cases through fixed-parameter algorithms, kernelization, and parameterized approximation. For graph partitioning, we obtain a subexponential fixed-parameter algorithm for Edge Cut on chordal graphs and polynomial-time algorithms for Vertex Cut on several structured graph classes. For Achromatic Number, we establish fixed-parameter tractability, derive polynomial kernels on forests and bounded-degeneracy graphs, and study structural parameterizations. For full covering problems, we show that Hyperedge Dominating Set is fixed-parameter tractable and admits a polynomial kernel when the maximum hyperedge size is bounded, while proving hardness without this restriction. We also obtain a fixed- parameter algorithm and a polynomial kernel for covering graph edges using a bounded number of short paths. The main approximation framework concerns weighted partial covering problems. We develop randomized and deterministic e”cient parameterized approximation schemes for Weighted Maximum Coverage on set systems whose incidence graphs have bounded semi-ladder index, together with one-additive parameterized algorithms for Weighted Partial Set Cover. The framework supports matroid and partition constraints and applies to several graph-theoretic and geometric covering problems. A structure-preserving reduction further yields approximation schemes for cardinality-constrained maximum satisfiability. Finally, for approval-based multiwinner elections with diminishing-return satisfaction functions, we obtain parameterized approximation schemes, additive approximations, lossy kernels, and exact parameterized algorithms under structural restrictions on approval profiles.