### Abstract

Original language | Undefined |
---|---|

Article number | 10.1016/j.tcs.2008.03.024 |

Pages (from-to) | 1319-1327 |

Number of pages | 9 |

Journal | Theoretical computer science |

Volume | 410 |

Issue number | 14 |

DOIs | |

Publication status | Published - Mar 2009 |

### Keywords

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

### Cite this

*Theoretical computer science*,

*410*(14), 1319-1327. [10.1016/j.tcs.2008.03.024]. https://doi.org/10.1016/j.tcs.2008.03.024

}

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

Research output: Contribution to journal › Article › Academic › peer-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 -