The Parameterized Complexity Landscape of Some Graph Problems

Abstract

The study of computational complexity has evolved significantly since the classification of the Boolean satisfiability problem as NP-complete in 1971. With thousands of problems now identified as NP-hard, understanding their tractability remains a central challenge, particularly under the widely held assumption that P ≠ NP. This thesis investigates the parameterized complexity of several fundamental graph-theoretic problems, providing new algorithmic insights and complexity classifications.

We analyze problems such as Harmless Set, Defensive Alliances, Offensive Alliances, Locally and Globally Minimal Alliances, and F-Free Edge Deletion, as well as the maximum minimal versions of classical problems like Minimum-Separator and Odd Cycle Transversal. Our research provides a comprehensive parameterized complexity landscape for these problems by establishing their fixed-parameter tractability (FPT) status, designing kernelization algorithms, and proving hardness results.

A key contribution of this thesis is the establishment of W[1]-hardness results for several problems, including Harmless Set, Defensive Alliance, and Offensive Alliance, when parameterized by restrictive structural parameters such as feedback vertex set number, pathwidth, treedepth, and cluster vertex deletion number. Additionally, we develop fixed-parameter tractable (FPT) algorithms for problems such as Harmless Set parameterized by vertex integrity, neighborhood diversity, and twin cover, as well as for Locally Minimal Defensive Alliance when parameterized by solution size. In terms of kernelization complexity, we show that Defensive Alliance does not admit a polynomial kernel when parameterized by vertex cover number, unless coNP is contained in NP/poly, and we establish an XP algorithm for this problem parameterized by clique-width. Moreover, we resolve open problems in the literature, such as proving the W[1]-hardness of Th+1-Free Edge Deletion parameterized by treewidth and determining the FPT classification of Maximum Minimal st-Separator parameterized by solution size. Finally, we introduce new kernelization techniques and subexponential algorithms for problems like Locally Minimal Defensive Alliance on special graph classes, including planar graphs.

Beyond their theoretical significance, these results have potential applications in network security, social influence analysis, and computational biology, where efficient structural modifications play a crucial role. By leveraging advanced tools from graph theory, combinatorial optimization, and algorithm design, this thesis provides a refined perspective on the tractability of NP-hard problems within the framework of parameterized complexity.