Upper bounds and algorithms for parallel knock-out numbers

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

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

Abstract

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.
Original languageUndefined
Article number10.1016/j.tcs.2008.03.024
Pages (from-to)1319-1327
Number of pages9
JournalTheoretical computer science
Volume410
Issue number14
DOIs
Publication statusPublished - Mar 2009

Keywords

  • IR-67840
  • METIS-263961
  • EWI-15828

Cite this

Broersma, H. J., Johnson, M., Paulusma, D., & Stewart, I. A. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical computer science, 410(14), 1319-1327. [10.1016/j.tcs.2008.03.024]. https://doi.org/10.1016/j.tcs.2008.03.024
Broersma, Haitze J. ; Johnson, Matthew ; Paulusma, Daniël ; Stewart, Iain A. / Upper bounds and algorithms for parallel knock-out numbers. In: Theoretical computer science. 2009 ; Vol. 410, No. 14. pp. 1319-1327.
@article{78d7eda7e30340aba979ff662ee65abb,
title = "Upper bounds and algorithms for parallel knock-out numbers",
abstract = "We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.",
keywords = "IR-67840, METIS-263961, EWI-15828",
author = "Broersma, {Haitze J.} and Matthew Johnson and Dani{\"e}l Paulusma and Stewart, {Iain A.}",
note = "10.1016/j.tcs.2008.03.024",
year = "2009",
month = "3",
doi = "10.1016/j.tcs.2008.03.024",
language = "Undefined",
volume = "410",
pages = "1319--1327",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",
number = "14",

}

Broersma, HJ, Johnson, M, Paulusma, D & Stewart, IA 2009, 'Upper bounds and algorithms for parallel knock-out numbers' Theoretical computer science, vol. 410, no. 14, 10.1016/j.tcs.2008.03.024, pp. 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

Upper bounds and algorithms for parallel knock-out numbers. / Broersma, Haitze J.; Johnson, Matthew; Paulusma, Daniël; Stewart, Iain A.

In: Theoretical computer science, Vol. 410, No. 14, 10.1016/j.tcs.2008.03.024, 03.2009, p. 1319-1327.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Upper bounds and algorithms for parallel knock-out numbers

AU - Broersma, Haitze J.

AU - Johnson, Matthew

AU - Paulusma, Daniël

AU - Stewart, Iain A.

N1 - 10.1016/j.tcs.2008.03.024

PY - 2009/3

Y1 - 2009/3

N2 - We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

AB - We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

KW - IR-67840

KW - METIS-263961

KW - EWI-15828

U2 - 10.1016/j.tcs.2008.03.024

DO - 10.1016/j.tcs.2008.03.024

M3 - Article

VL - 410

SP - 1319

EP - 1327

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

IS - 14

M1 - 10.1016/j.tcs.2008.03.024

ER -

Broersma HJ, Johnson M, Paulusma D, Stewart IA. Upper bounds and algorithms for parallel knock-out numbers. Theoretical computer science. 2009 Mar;410(14):1319-1327. 10.1016/j.tcs.2008.03.024. https://doi.org/10.1016/j.tcs.2008.03.024