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

Broersma, H. J., Johnson, M., Paulusma, D., & Stewart, I. A. (2006). The Computational Complexity of the Parallel Knock-Out Problem. In J. R. Correa, A. Hevia, & M. Kiwi (Eds.), Proceedings of the 7th Latin American Symposium (LATIN 2006) (pp. 250-261). [10.1007/11682462_26] (Lecture Notes in Computer Science; Vol. 3887, No. 11). Berlin: Springer. https://doi.org/10.1007/11682462_26
Broersma, Haitze J. ; Johnson, M. ; Paulusma, Daniël ; Stewart, I.A. / The Computational Complexity of the Parallel Knock-Out Problem. Proceedings of the 7th Latin American Symposium (LATIN 2006). editor / J.R. Correa ; A. Hevia ; M. Kiwi. Berlin : Springer, 2006. pp. 250-261 (Lecture Notes in Computer Science; 11).
@inproceedings{a9a15a15b53a4579942026b991605c9e,
title = "The Computational Complexity of the Parallel Knock-Out Problem",
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.",
keywords = "EWI-8091, IR-63665, METIS-238711",
author = "Broersma, {Haitze J.} and M. Johnson and Dani{\"e}l Paulusma and I.A. Stewart",
note = "10.1007/11682462_26",
year = "2006",
doi = "10.1007/11682462_26",
language = "Undefined",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "11",
pages = "250--261",
editor = "J.R. Correa and A. Hevia and M. Kiwi",
booktitle = "Proceedings of the 7th Latin American Symposium (LATIN 2006)",

}

Broersma, HJ, Johnson, M, Paulusma, D & Stewart, IA 2006, The Computational Complexity of the Parallel Knock-Out Problem. in JR Correa, A Hevia & M Kiwi (eds), Proceedings of the 7th Latin American Symposium (LATIN 2006)., 10.1007/11682462_26, Lecture Notes in Computer Science, no. 11, vol. 3887, Springer, Berlin, pp. 250-261. https://doi.org/10.1007/11682462_26

The Computational Complexity of the Parallel Knock-Out Problem. / Broersma, Haitze J.; Johnson, M.; Paulusma, Daniël; Stewart, I.A.

Proceedings of the 7th Latin American Symposium (LATIN 2006). ed. / J.R. Correa; A. Hevia; M. Kiwi. Berlin : Springer, 2006. p. 250-261 10.1007/11682462_26 (Lecture Notes in Computer Science; Vol. 3887, No. 11).

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

TY - GEN

T1 - The Computational Complexity of the Parallel Knock-Out Problem

AU - Broersma, Haitze J.

AU - Johnson, M.

AU - Paulusma, Daniël

AU - Stewart, I.A.

N1 - 10.1007/11682462_26

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - EWI-8091

KW - IR-63665

KW - METIS-238711

U2 - 10.1007/11682462_26

DO - 10.1007/11682462_26

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 250

EP - 261

BT - Proceedings of the 7th Latin American Symposium (LATIN 2006)

A2 - Correa, J.R.

A2 - Hevia, A.

A2 - Kiwi, M.

PB - Springer

CY - Berlin

ER -

Broersma HJ, Johnson M, Paulusma D, Stewart IA. The Computational Complexity of the Parallel Knock-Out Problem. In Correa JR, Hevia A, Kiwi M, editors, Proceedings of the 7th Latin American Symposium (LATIN 2006). Berlin: Springer. 2006. p. 250-261. 10.1007/11682462_26. (Lecture Notes in Computer Science; 11). https://doi.org/10.1007/11682462_26