Upper bounds and algorithms for parallel knock-out numbers

Haitze J. Broersma, Matthew Johnson, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (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 show that, for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{\alpha}$, where $\alpha$ is the independence number of $G$. This upper bound is tight and the result implies the square-root conjecture which was first posed in MFCS 2004. 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.
Original languageUndefined
Title of host publicationSIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity
EditorsGiuseppe Prencipe, Shmuel Zaks
Place of PublicationBerlin
PublisherSpringer
Pages328-340
Number of pages13
DOIs
Publication statusPublished - Jul 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Number1
Volume4474
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • EWI-11586
  • IR-62061
  • METIS-245868

Cite this

Broersma, H. J., Johnson, M., & Paulusma, D. (2007). Upper bounds and algorithms for parallel knock-out numbers. In G. Prencipe, & S. Zaks (Eds.), SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity (pp. 328-340). [10.1007/978-3-540-72951-8_26] (Lecture Notes in Computer Science; Vol. 4474, No. 1). Berlin: Springer. https://doi.org/10.1007/978-3-540-72951-8_26