2016/09/10 by Fiala, Jiří, Klavík, Pavel, Kratochvíl, Jan +1 · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)
paper · doi:10.48550/arxiv.1609.03013
A graph G covers a graph H if there exists a locally bijective homomorphism from G to H. We deal with regular covers where this homomorphism is prescribed by the action of a semiregular subgroup of \textrmAut(G). We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for given graphs G and H whether G regularly covers H. When |H|=1, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for |G| = |H| when it becomes the graph isomorphism problem. Our main result is an involved FPT algorithm solving RegularCover for planar inputs G in time O^*(2e(H)/2) where e(H) denotes the number of edges of H. The algorithm is based on dynamic programming and employs theoretical results proved in a related structural paper. Further, when G is 3-connected, H is 2-connected or the ratio |G|/|H| is an odd integer, we can solve the problem RegularCover in polynomial time. In comparison, Bílka et al. (2011) proved that testing general graph covers is NP-complete for planar inputs G when H is a small fixed graph such as K4 or K5.