Paper Info
Title
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs.
Abstract
A graph G covers a graph H if there exists a locally bijective homomorphism from G to H. We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a subgroup of Aut(G). Regular covers have many applications in constructions and studies of big objects all over mathematics and computer science. We study computational aspects of regular covers that have not been addressed before. The decision problem REGULARCOVER asks for two given graphs G and H whether G regularly covers H. When vertical bar H vertical bar = 1, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for vertical bar G vertical bar = vertical bar H vertical bar when it becomes the graph isomorphism problem. Therefore, we restrict ourselves to graph classes with polynomially solvable graph isomorphism. Inspired by Negami, we apply the structural results used by Babai in the 1970's to study automorphism groups of graphs. Our main result is an FPT algorithm solving REGULARCOVER for planar input G in time O*(2(e(H)/2)) where e(H) denotes the number of the edges of H. In comparison, testing general graph covers is known to be NP-complete for planar inputs G even for small fixed graphs H such as K-4 or K-5. Most of our results also apply to general graphs, in particular the complete structural understanding of regular covers for 2-cuts.
Year
DOI
Venue
2014
10.1007/978-3-662-43948-7_41
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8572
0302-9743
Citations 
PageRank 
References 
5
0.42
21
Authors
4
Name
Order
Citations
PageRank
Jirí Fiala126422.48
Pavel Klavík29510.63
Jan Kratochvíl31751151.84
Roman Nedela439247.78