The computational complexity of the parallel knock-out problem

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

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    7 Downloads (Pure)

    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 bipartite 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 bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) $k$ rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that $r$-regular graphs with $r\ge 1$, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.
    Original languageEnglish
    Pages (from-to)182-195
    Number of pages14
    JournalTheoretical computer science
    Volume393
    Issue number1-3
    DOIs
    Publication statusPublished - Mar 2008
    Event7th Latin American Symposium on Theoretical Informatics, LATIN 2006 - Valdivia, Chile
    Duration: 20 Mar 200624 Mar 2006
    Conference number: 7

    Fingerprint

    Dive into the research topics of 'The computational complexity of the parallel knock-out problem'. Together they form a unique fingerprint.
    • The Computational Complexity of the Parallel Knock-Out Problem

      Broersma, H., Johnson, M., Paulusma, D. & Stewart, I. A., 2006, LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings. Correa, J. R., Hevia, A. & Kiwi, M. (eds.). Berlin: Springer, p. 250-261 12 p. (Lecture Notes in Computer Science; vol. 3887).

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

      2 Citations (Scopus)
      1 Downloads (Pure)

    Cite this