The Computational Complexity of the Parallel Knock-Out Problem

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

doi:10.1007/11682462_26

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 proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

1 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 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 language	English
Title of host publication	LATIN 2006: Theoretical Informatics
Subtitle of host publication	7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings
Editors	José R Correa, Alejandro Hevia, Marcos Kiwi
Place of Publication	Berlin
Publisher	Springer
Pages	250-261
Number of pages	12
ISBN (Electronic)	978-3-540-32756-1
ISBN (Print)	978-3-540-32755-4
DOIs	https://doi.org/10.1007/11682462_26
Publication status	Published - 2006
Event	7th Latin American Symposium on Theoretical Informatics, LATIN 2006 - Valdivia, Chile Duration: 20 Mar 2006 → 24 Mar 2006 Conference number: 7

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3887
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th Latin American Symposium on Theoretical Informatics, LATIN 2006
Abbreviated title	LATIN
Country/Territory	Chile
City	Valdivia
Period	20/03/06 → 24/03/06

Access to Document

10.1007/11682462_26

The computational complexity of the parallel knock-out problem
Broersma, H., Johnson, M., Paulusma, D. & Stewart, I. A., Mar 2008, In: Theoretical computer science. 393, 1-3, p. 182-195 14 p.
Research output: Contribution to journal › Article › Academic › peer-review
5 Link opens in a new tab Citations (Scopus)

7 Downloads (Pure)

Cite this

Broersma, H., 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.), LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings (pp. 250-261). (Lecture Notes in Computer Science; Vol. 3887). Springer. https://doi.org/10.1007/11682462_26

Broersma, Hajo ; Johnson, Matthew ; Paulusma, Daniël et al. / The Computational Complexity of the Parallel Knock-Out Problem. LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings. editor / José R Correa ; Alejandro Hevia ; Marcos Kiwi. Berlin : Springer, 2006. pp. 250-261 (Lecture Notes in Computer Science).

@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 \textbackslash{}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.",

author = "Hajo Broersma and Matthew Johnson and Dani{\"e}l Paulusma and Stewart, \{Iain A.\}",

year = "2006",

doi = "10.1007/11682462\_26",

language = "English",

isbn = "978-3-540-32755-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "250--261",

editor = "Correa, \{Jos{\'e} R\} and Alejandro Hevia and Marcos Kiwi",

booktitle = "LATIN 2006: Theoretical Informatics",

address = "Germany",

note = "7th Latin American Symposium on Theoretical Informatics, LATIN 2006, LATIN ; Conference date: 20-03-2006 Through 24-03-2006",

}

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

The Computational Complexity of the Parallel Knock-Out Problem. / Broersma, Hajo; Johnson, Matthew; Paulusma, Daniël et al.
LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings. ed. / José R Correa; Alejandro Hevia; Marcos Kiwi. Berlin: Springer, 2006. p. 250-261 (Lecture Notes in Computer Science; Vol. 3887).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Broersma, Hajo

AU - Johnson, Matthew

AU - Paulusma, Daniël

AU - Stewart, Iain A.

N1 - Conference code: 7

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.

U2 - 10.1007/11682462_26

DO - 10.1007/11682462_26

M3 - Conference contribution

SN - 978-3-540-32755-4

T3 - Lecture Notes in Computer Science

SP - 250

EP - 261

BT - LATIN 2006: Theoretical Informatics

A2 - Correa, José R

A2 - Hevia, Alejandro

A2 - Kiwi, Marcos

PB - Springer

CY - Berlin

T2 - 7th Latin American Symposium on Theoretical Informatics, LATIN 2006

Y2 - 20 March 2006 through 24 March 2006

ER -

The Computational Complexity of the Parallel Knock-Out Problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

The computational complexity of the parallel knock-out problem

Cite this