Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective

Chuan-Min Lee ()
Additional contact information
Chuan-Min Lee: Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan

Mathematics, 2023, vol. 11, issue 15, 1-33

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/15/3325/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/15/3325/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:15:p:3325-:d:1205457

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().