IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i15p3325-d1205457.html
   My bibliography  Save this article

Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective

Author

Listed:
  • Chuan-Min Lee

    (Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan)

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.

Suggested Citation

  • Chuan-Min Lee, 2023. "Clique Transversal Variants on Graphs: A Parameterized-Complexity Perspective," Mathematics, MDPI, vol. 11(15), pages 1-33, July.
    • Handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3325-:d:1205457
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/15/3325/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/11/15/3325/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Mihaela Aurelia Tomescu & Lorentz Jäntschi & Doina Iulia Rotaru, 2021. "Figures of Graph Partitioning by Counting, Sequence and Layer Matrices," Mathematics, MDPI, vol. 9(12), pages 1-25, June.
    2. Chuan-Min Lee, 2010. "Variations of maximum-clique transversal sets on graphs," Annals of Operations Research, Springer, vol. 181(1), pages 21-66, December.
    3. Ke Liu & Mei Lu, 2021. "Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs," Journal of Combinatorial Optimization, Springer, vol. 41(4), pages 923-933, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.

      Corrections

      All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:11:y:2023:i:15:p:3325-:d:1205457. See general information about how to correct material in RePEc.

      If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

      If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

      If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

      For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

      Please note that corrections may take a couple of weeks to filter through the various RePEc services.

      IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.