Algorithmic Aspects of Regular Graph Covers

Authors Jiří Fiala, Pavel Klavík, Jan Kratochvíl, Roman Nedela

Publication date 10 September 2016

Abstract: 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

e x t r m A u t (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^{*} (2^{e (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'ilka 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

K_{4}

or

K_{5}

.

This page was built for publication: Algorithmic Aspects of Regular Graph Covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6277377)