The Parameterized Complexity of Graph Editing & MaxMin Problems

Abstract

This thesis presents a comprehensive study of the parameterized complexity of several graph-theoretic problems, with a focus on graph modification, separation, and vertex splitting. The investigation is primarily motivated by two thematic directions: enforcing structural properties in graphs via modification operations, and analyzing maximization problems that seek large minimal solutions under certain constraints (commonly referred to as MaxMin problems). We begin with an in-depth analysis of Uniform Cluster Graph Modification problems, where the objective is to transform a given graph into a disjoint union of equal-sized cliques using a limited number of edit operations, including vertex deletion, edge deletion, edge addition, edge editing, and vertex splitting. For various problem variants, we provide improved fixed-parameter tractable (FPT) algorithms and kernelization results, including both polynomial and linear kernels. Our contributions resolve several open questions posed in the existing literature on these problems. Subsequently, we examine a range of MaxMin Problems, such as MaxMin Degree-dModulator and MaxMin Feedback Vertex Set. We extend known results for special cases, establish new kernelization bounds, and design FPT algorithms under natural structural parameters, including vertex cover and treewidth. We also study generalizations of classical separation problems by introducing and analyzing the MaxMin Multiway Cut-Uncut, MaxMin Separator-Unseparator, and MaxMin Subset Feedback Vertex Set problems, presenting both algorithmic results and hardness proofs with respect to various parameterizations. Finally, the thesis investigates the computational complexity of F-Vertex Splitting for different graph classes under both inclusive and exclusive splitting models. We provide a fine-grained complexity classification, proving NP-hardness for several variants. Overall, this work advances the theoretical understanding of graph modification, separation, and vertex splitting problems within the framework of parameterized complexity, offering novel algorithmic techniques, kernelization bounds, and hardness results for a broad spectrum of combinatorial problems.