Result: Large-girth roots of graphs
Title:
Large-girth roots of graphs
Authors:
Contributors:
Department of Computer Science and DIMAP, University of Warwick [Coventry], Warwick Mathematics Institute and DIMAP, Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :35-46
Publisher Information:
CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
collection:TDS-MACS
collection:TDS-MACS
Subject Terms:
Graph roots, Graph powers, NP-completeness, Recognition algorithms, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.2: Graph Theory, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM]
Subject Geographic:
Original Identifier:
HAL:
Document Type:
Conference
conferenceObject<br />Conference papers
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00454554v1
Database:
HAL
Further Information
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.