Exploring Clique Transversal Problems for <i>d</i>-degenerate Graphs with Fixed <i>d</i>: From Polynomial-Time Solvability to Parameterized Complexity

Abstract

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.

Keywords

• signed clique transversal
• minus clique transversal
• <i>b</i>-fold clique transversal
• {<i>b</i>}-clique transversal
• fixed parameter tractable
• para-NP-complete