Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective

Abstract

The clique transversal problem and its variants have garnered significant attention in the last two decades due to their practical applications in communication networks, social-network theory and transceiver placement for cellular telephones. While previous research primarily focused on determining the polynomial-time solvability or NP-hardness/NP-completeness of specific graphs, this paper adopts a parameterized-complexity approach. It thoroughly explores four clique transversal variants: the d-fold transversal problem, the {d}-clique transversal problem, the signed clique transversal problem and the minus clique transversal problem. The paper presents various findings regarding the parameterized complexity of the clique transversal problem and its variants. It establishes the W[2]-completeness and para-NP-completeness of the d-fold transversal problem, the {d}-clique transversal problem, the signed clique transversal problem and the minus clique transversal problem within specific graph classes. Additionally, it introduces fixed-parameter tractable algorithms for planar graphs and graphs with bounded treewidth, offering efficient solutions for these specific instances of the problems. The research further explores the relationship between planar graphs and graphs with bounded treewidth to enhance the time complexity of the d-fold clique transversal problem and the {d}-clique transversal problem. By analyzing the parameterized complexity of the clique transversal problem and its variants, this research contributes to our understanding of the computational limitations and potentially efficient algorithms for solving these problems.

Keywords

• parameterized complexity
• W-hierarchy
• NP-completeness
• clique transversal function
• treewidth
• subcubic graph