The Computational Complexity of the Parallel Knock-Out Problem

Haitze J. Broersma, M. Johnson, Daniël Paulusma, I.A. Stewart

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

1 Citation (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 languageUndefined
Title of host publicationProceedings of the 7th Latin American Symposium (LATIN 2006)
EditorsJ.R. Correa, A. Hevia, M. Kiwi
Place of PublicationBerlin
PublisherSpringer
Pages250-261
Number of pages12
DOIs
Publication statusPublished - 2006

Publication series

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

Keywords

  • EWI-8091
  • IR-63665
  • METIS-238711

Cite this