# Upper bounds and algorithms for parallel knock-out numbers

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

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 language Undefined 10.1016/j.tcs.2008.03.024 1319-1327 9 Theoretical computer science 410 14 https://doi.org/10.1016/j.tcs.2008.03.024 Published - Mar 2009

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