Large-girth roots of graphs

Abstract : We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all r-th roots of a given graph that have girth at least 2r+3 and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for r=2,3.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.35-46, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00454554
Contributor : Publications Loria <>
Submitted on : Monday, February 8, 2010 - 5:29:45 PM
Last modification on : Monday, February 8, 2010 - 5:34:28 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:36:30 PM

File

adamaszek.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00454554, version 1

Collections

Citation

Anna Adamaszek, Michal Adamaszek. Large-girth roots of graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.35-46, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00454554>

Share

Metrics

Record views

117

Document downloads

100