The Computational Complexity of the Parallel Knock-Out Problem

Hajo Broersma, Matthew Johnson, Daniël Paulusma, Iain A. Stewart

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    2 Citations (Scopus)

    Abstract

    We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers $k \ge 2$, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most $k$ rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.
    Original languageEnglish
    Title of host publicationLATIN 2006: Theoretical Informatics
    Subtitle of host publication7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings
    EditorsJosé R Correa, Alejandro Hevia, Marcos Kiwi
    Place of PublicationBerlin
    PublisherSpringer
    Pages250-261
    Number of pages12
    ISBN (Electronic)978-3-540-32756-1
    ISBN (Print)978-3-540-32755-4
    DOIs
    Publication statusPublished - 2006
    Event7th Latin American Symposium on Theoretical Informatics, LATIN 2006 - Valdivia, Chile
    Duration: 20 Mar 200624 Mar 2006
    Conference number: 7

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume3887
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference7th Latin American Symposium on Theoretical Informatics, LATIN 2006
    Abbreviated titleLATIN
    CountryChile
    CityValdivia
    Period20/03/0624/03/06

    Fingerprint

    Dive into the research topics of 'The Computational Complexity of the Parallel Knock-Out Problem'. Together they form a unique fingerprint.

    Cite this