Exploring Clique Transversal Problems for d -degenerate Graphs with Fixed d : From Polynomial-Time Solvability to Parameterized Complexity.

This paper explores the computational challenges of clique transversal problems in d-degenerate graphs, which are commonly encountered across theoretical computer science and various network applications. We examine d-degenerate graphs to highlight their utility in representing sparse structures and assess several variations of clique transversal problems, including the b-fold and { b } -clique transversal problems, focusing on their computational complexities for different graph categories. Our analysis identifies that certain instances of these problems are polynomial-time solvable in specific graph classes, such as 1-degenerate or 2-degenerate graphs. However, for d-degenerate graphs where d ≥ 2 , these problems generally escalate to NP-completeness. We also explore the parameterized complexity, pinpointing specific conditions that render these problems fixed-parameter tractable. [ABSTRACT FROM AUTHOR]