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