ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS∗

arXiv:1609.03013v2 [cs.DM] 29 Jan 2017

JIŘÍ FIALA† , PAVEL KLAVÍK‡ , AND JAN KRATOCHVÍL† AND ROMAN NEDELA§ , ¶
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 Aut(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 .
Key words. regular graph covers, planar graphs, FPT algorithm, computational complexity, graph isomorphism problem,
Cayley graph recognition

1. Introduction. The notion of covering originates in topology as a notion of local similarity of two
topological spaces. For instance, consider the unit circle and the real line. Globally, these two spaces are not
the same, they have different properties, different fundamental groups, etc. But when we restrict ourselves
to a small part of the circle, it looks the same as a small part of the real line; more precisely the two spaces
are locally homeomorphic, and thus they share the local properties. The notion of covering formalizes this
property of two spaces being locally the same.
Suppose that we have two topological spaces: a big one G and a small one H. We say that G covers H if
there exists an epimorphism called a covering projection p : G → H which locally preserves the structure of
G. For instance, the mapping p(x) = (cos x, sin x) from the real line to the unit circle is a covering projection.
The existence of a covering projection ensures that G looks locally the same as H; see Fig. 1.1a.
In this paper, we study coverings of graphs in a more restricting version called regular covering, for which
the covering projection is described by an action of a group; see Section 2 for the formal definition. If G
regularly covers H, then we say that H is a (regular) quotient of G.
Negami’s Theorem [52], stating that all regular quotients of planar graphs can be embedded into the
projective plane, is one of the oldest results in topological graph theory. Therefore, we have decided to
initiate the study of computational complexity of regular graph covers with planar graphs.
1.1. Applications of Graph Coverings. Suppose that G covers H and we have some information
about one of the objects. How much knowledge does translate to the other object? It turns out that quite
a lot, and this makes covering a powerful technique with many diverse applications. The big advantage of
regular coverings is that they can be efficiently described and many properties easily translate between the
objects. We sketch some applications now.
Powerful Constructions. The reverse of covering called lifting can be applied to small objects in order to
construct large objects of desired properties. For instance, the well-known Cayley graphs are large objects
which can be described easily by a few elements of a group. Let G be a Cayley graph generated by elements
g1 , . . . , ge of a group Γ. The vertices of G correspond to the elements of Γ and the edges are described by
∗ This paper continues the research started in ICALP 2014 [25] and extends its results. For a structural diagram visualizing
our results, see http://pavel.klavik.cz/orgpad/regular_covers.html (supported for Firefox and Google Chrome). This work
was initiated during workshops Algebraic, Topological and Complexity Aspects of Graph Covers (ATCACG). The authors are
supported by CE-ITI (P202/12/G061 of GAČR). The first author is also supported by the project Kontakt LH12095, the
second and the third authors by Charles University as GAUK 196213, the fourth author by the Ministry of Education of
the Slovak Republic, the grant VEGA 1/0150/14, by Project LO1506 of the Czech Ministry of Education and by the project
APVV-15-0220.
† Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Malostranské náměstı́ 25,
118 00 Prague, Czech Republic.
E-mails: {fiala,honza}@kam.mff.cuni.cz.
‡ Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Malostranské náměstı́ 25, 118 00
Prague, Czech Republic. E-mail: klavik@iuuk.mff.cuni.cz.
§ Institute of Mathematics and Computer Science SAS, Ďumbierska 1, 974 11 Banská Bystrica, Slovak republic. Email:
nedela@savbb.sk.
¶ European Centre of Excellence NTIS, University of West Bohemia, Pilsen, Czech Republic.

1

2

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

x

w
u

u
v
y

y
w

v

p

y

v

x

w

x

G

u

H

(a)

(b)

Fig. 1.1. (a) A covering projection p from a graph G to a graph H. (b) The Cayley graph of the dihedral group D4
generated by the 90◦ rotations (in black) and the reflection around the x-axis (in white).

actions of g1 , . . . , ge on Γ by left multiplication; each gi defines a permutation on Γ and we put edges along
the cycles of this permutation. See Fig. 1.1b for an example. Cayley graphs were originally invented to study
the structure of groups [16].
In the language of coverings, every Cayley graph G can be described as a lift of a one vertex graph H
with e loops and half-edges attached labeled g1 , . . . , ge . Regular covers can be viewed as a generalization of
Cayley graphs where the small graph H can contain more than one vertex. For example, the famous Petersen
graph can be constructed as a lift of a two-vertex graph H in Fig. 1.2a. These two vertices are necessary as
it is known that Petersen graph is not a Cayley graph. Figure 1.2b shows a simple construction [50, 58] of
the Hoffman-Singleton graph [35] which is a 7-regular graph with 50 vertices.
The Petersen and the Hoffman-Singleton graphs are extremal graphs for the degree-diameter problem:
given integers d and k, find a maximal graph G with diameter d and degree k. In general, the size of G is
not known. Many currently best constructions were obtained using the covering techniques [51].
Further applications employ the fact that nowhere-zero flows, vertex and edge colorings, eigenvalues
and other graph invariants lift along a covering projection. Two main applications of constructions of lifts
are the solution of the Heawood map coloring problem [53, 31] and constructions of arbitrarily large highly
symmetrical graphs [10].
Models of Local Computation. These and similar constructions have many practical applications in
designing highly efficient computer networks [20, 2, 9, 13, 14, 15, 32, 60], since these networks can be
efficiently described/constructed and have many strong properties. In particular, networks based on covers
of simple graphs allow fast parallelization of computation as described e.g. in [12, 3, 4].
Simplifying Objects. Regular coverings can be also applied in the opposite way, to project big objects
onto smaller ones while preserving some properties. One way is to represent a class of objects satisfying
some properties as quotients of the universal object of this property. For instance, this was used in the study
of arc-transitive cubic graphs [30], and the key point is that universal objects are much easier to work with.
This idea is commonly used in fields such as the theory of Riemann surfaces [22] and theoretical physics [40].
1.2. Regular Covering Testing. Despite all described applications, the computational complexity of
regular covering was not yet studied. In this paper, we initiate the study of the following computational
problem.

0
{(k, k 2 ) : ∀k ∈ C5 }
1

0

2

C5

1

4

(1, 0)

(a)

(2, 0)

(b)
3

2

Fig. 1.2. (a) A construction of the Petersen graph by lifting with the group C5 . (b) By lifting the described graph with
the group C25 , we get the Hoffman-Singleton graph. The five parallel edges are labeled (0, 0), (1, 1), (2, 4), (3, 4) and (4, 1).

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

Problem:
Input:
Output:

3

RegularCover
Connected graphs G and H.
Does G regularly cover H?

For a fixed graph H, the computational complexity of RegularCover was first asked as an open
problem by Abello et al. [1]: “Are there graphs H for which the problem of determining if an input graph
G is a regular cover of H is NP-hard?” Currently, no NP-hardness reduction is known for RegularCover,
even when H is a part of the input. Our main result shows that if G is planar, no such graph H exists.
We use the complexity notation f = O∗ (g) which omits polynomial factors. We establish the following FPT
algorithm:
Theorem 1.1. For planar graphs G, the RegularCover problem can be solved in time O∗ (2e(H)/2 ),
where e(H) is the number of edges of H.
1.3. Related Computational Problems. We discuss other computational problems related to RegularCover. The notion of regular covers builds a bridge between two seemingly different problems: Cayley
graph recognition and the graph isomorphism problem.
Covering Testing. The complexity of general covering was widely studied before, pioneered by Bodlaender [12] in the context of networks of processors in parallel computing. Abello et al. [1] introduced the
H-Cover problem which asks for an input graph G whether it covers a fixed graph H. Unless H is very
simple, the problem turned out to be mostly NP-complete, the general complexity is still unresolved but the
papers [45, 24] show that it is NP-complete for every r-regular graph H where r ≥ 3. For a survey of the
complexity results, see [27].
We try to understand how much the additional algebraic structure of regular covering changes the
computational complexity. For planar inputs G, the change is significant: the problem H-Cover remains
NP-complete for several small fixed graphs H (such as K4 , K5 ) [11], while RegularCover can be solved
in polynomial time for every fixed graph H by Theorem 1.1.
Cayley Graphs Testing. If the graph H consists of a single vertex with attached loops and half-edges,
it corresponds to Cayley graph recognition whose computational complexity is widely open. No hardness
results are known and a polynomial-time algorithm is known only for recognition of circulant graphs [21].
In contrast, if H consists of a vertex with three half-edges attached, then G covers H if and only if G is a
cubic 3-edge-colorable graph, so H-Cover is NP-complete [36].
The reader may notice that Theorem 1.1 gives a polynomial time algorithm to recognize planar Cayley
graphs. The input is a k-regular planar graph G, for k ≤ 5. We test RegularCover for all graphs H which
a single vertex of degree k. Unfortunately, finite planar Cayley graphs G are very limited: either G is a cycle,
or G is 3-connected. Therefore, Aut(G) is a spherical group which is very simple. Therefore, G is either
finite (with v(G) ≤ 120), representing one of the sporadic groups (for instance, a truncated dodecahedron is
a Cayley graph of A5 ), or very simple (a cycle, a prism, an antiprism, e.g.).
Graph Isomorphism Problem. The other extreme is when both graphs G and H have the same size, for
which RegularCover is the famous graph isomorphism problem (GraphIso). Graph isomorphism belongs
to NP, it is unlikely NP-complete, however no polynomial-time algorithm is known and Babai [8] recently
proved that it can be solved in quasipolynomial time. Also, polynomial-time algorithms for GraphIso are
known for many graph classes and parameters; see [41] for an overview. Since RegularCover generalizes
GraphIso, we cannot hope to solve it in polynomial time (unless solving GraphIso as well). It is natural
to ask which results and techniques for GraphIso translate to RegularCover. Our results show that
some technique for planar graphs translate, but the RegularCover problem is significantly more involved.
Theoretical motivation for studying the graph isomorphism problem is very similar to RegularCover.
For practical instances, one can solve GraphIso very efficiently using various heuristics. But polynomialtime algorithm working for all graphs is not known and it is very desirable to understand the complexity
of GraphIso. It is known that testing graph isomorphism is equivalent to testing isomorphism of general
mathematical structures [33]. The notion of isomorphism is widely used in mathematics when one wants
to show that two seemingly different structures are the same. One proceeds by guessing a mapping and
proving that this mapping is an isomorphism. The natural complexity question is whether there is a better
algorithmic way to derive an isomorphism. Similarly, regular covering is a well-known mathematical notion
which is algorithmically interesting and not understood.

4

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Computing Automorphism Groups. A regular covering is described by a semiregular subgroup of the
automorphism group Aut(G). We denote the computational problem of finding generators of Aut(G) by
AutGroup. Since a good understanding of Aut(G) is needed to solve RegularCover, it is closely related
to AutGroup.
It is known that GraphIso can be reduced to AutGroup (which forms the foundation of group theory
techniques used to attack the graph isomorphism problem, e.g., [48, 8]), moreover AutGroup can be solved
by O(n3 ) instances of GraphIso [49]. Surprisingly not much is known about automorphism groups of
restricted classes of graphs. Jordan [39] gave an inductive characterization of automorphism groups of trees
as the class of groups closed under direct product and wreath product with symmetric groups. Babai [5, 7]
described automorphism groups of planar graphs. Recently, Jordan-like characterizations of automorphism
groups of interval, circle and permutation graphs are given in [43, 44]. The AutGroup problem can be
solved in linear time for trees and interval graphs [18], in linear time for permutation graphs [44], and in
polynomial time for circle graphs [44].
Our description of semiregular actions on planar graphs in [26] was generalized in [42] to describe a
Jordan-like characterization of automorphism groups of planar graphs, which is much more detailed than
Babai’s description in [5]. It also implies a quadratic-time algorithm for AutGroup of planar graphs
(which likely can be improved to linear time), faster than the best previous trivial O(n4 ) algorithm by
combining [38, 49].
List Restricted Isomorphism Problem. Let G and H be graphs and the vertices of G be equipped by
lists: for each u ∈ V (G), we have L(u) ⊆ V (H). An isomorphism π : G → H is called list-compatible if
for every u ∈ V (G), we have π(u) ∈ L(u). The existence of a list-compatible isomorphism is denoted by
L
G −→
H.
Problem:
Input:
Output:

ListIso
Graph G and H, and for each u ∈ V (G) a list L(u) ⊆ V (H).
L
Does G −→
H?

This problem was first introduced by Lubiw [47] and proved to be NP-complete, even in the following
restricted setting.
Theorem 1.2 (Lubiw [47]). Testing existence of a fixed-point free involutory automorphism is NPcomplete.
But only the above result of [47] is cited while the ListIso problem was forgotten. We have rediscovered
ListIso since it was solved in a subroutine in our algorithm of Theorem 1.1 for 3-connected planar and
projectively planar graphs, for which it can be solved in polynomial time using [46]; see [25]. Our paper
gives a nice motivation for ListIso, leading Klavı́k et al. [41] to study it for many restricted graph classes
and parameters. In particular, ListIso can be solved in polynomial time for graphs of bounded genus and
bounded treewidth [41].
We also consider special instances called ColorIso in which both graphs G and H are colored and
c
we ask for existence of a color-preserving isomorphism, denoted G −→
H. Unlike ListIso, the ColorIso
problem is a well known problem which is polynomial-time equivalent to GraphIso.
Homomorphisms and CSP. Since regular covering is a locally bijective homomorphism, we give an
overview of complexity results concerning homomorphisms. Hell and Nešetřil [34] studied the problem HHom which asks whether there exists a homomorphism between an input graph G and a fixed graph H. Their
celebrated dichotomy result for simple graphs states that the problem H-Hom is polynomially solvable if H
is bipartite, and it is NP-complete otherwise. Homomorphisms can be described in the language of constraint
satisfaction (CSP), and the famous dichotomy conjecture [23] claims that every CSP is either polynomially
solvable, or NP-complete.
1.4. Other Covering Problems. We introduce and discuss several other problems related to (regular)
graph covering.
Lifting and Quotients. In the RegularCover problem, the input gives two graphs G and H. For the
following problems, the input specifies only one graph and we ask for existence of the other graph:

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

Problem:
Input:
Output:

RegularLifting
A connected graph H and an integer k.
Does there exists a graph G regularly covering H
such that |G| = k|H|?

Problem:
Input:
Output:

RegularQuotient
A connected graph G and an integer k.
Does there exists a graph H regularly covered by G
such that |H| = |G|
k ?

5

Concerning RegularLifting, the answer is always positive. The theory of covering describes a technique called voltage assignment which can be applied to generate all k-folds G. We do not deal with lifting
in this paper, but there are nevertheless many interesting computational questions with applications. For
instance, is it possible to generate efficiently all (regular) lifts up to isomorphism? (This is non-trivial
since different voltage assignments might lead to isomorphic graphs.) Or, does there exists a lift with some
additional properties?
Concerning RegularQuotient, by Theorem 1.2, this problem is NP-complete even for the fixed k = 2.
(We ask for existence of a half-quotient H of G which is equivalent to existence of a fixed-point free involution
in Aut(G).) This hardness reduction can be easily generalized for every fixed even k, but the complexity
remains open for odd values of k.
The reduction of Theorem 1.2 is from 3-satisfiability, each variable is represented by a variable gadget
which is an even cycle attached to the rest of the graph. Each cycle has two possible regular quotients, either
the cycle of half length (obtained by the 180◦ rotation), or the path of half length with attached half-edges
(obtained by a reflection through opposite edges), corresponding to true and false values, respectively. These
variable gadgets are attached to clause gadgets, and a quotient of a clause gadget can be constructed if and
only if at least one literal of the clause is satisfied. This reduction does not imply NP-completeness for the
RegularCover problem since the input also gives a graph H, so one can decode the assignment of the
variables from it.
k-Fold Covering. To simplify the RegularCover problem, instead of fixing H, we can fix the ratio
k = |G|/|H|. (When G covers H, then k is an integer.) We get the following two problems for general and
regular graph covers, respectively:
Problem:
Input:
Output:

k-Fold(Regular)Cover
Connected graphs G and H such that |G| = k|H|.
Does G (regularly) cover H?

For k = 1, both problems are equivalent to GraphIso. Bodlaender [12] proved that the k-FoldCover
problem is GI-hard for every fixed k (meaning that GraphIso can be reduced to it). The same reduction
also works for k-FoldRegularCover, see Lemma 2.3. Chaplick et al. [17] proved NP-completeness of
3-FoldCover and their reduction can be easily modified for all k > 3. The complexities of 2-FoldCover
and k-FoldRegularCover for all k ≥ 2 are open and very interesting. We note that for k = 2, every
covering is a regular covering, so the problems 2-FoldRegularCover and 2-FoldCover are identical,
and NP-hardness of 2-FoldCover would imply NP-hardness for RegularCover as well. On the other
hand, if k-FoldRegularCover is not NP-complete for any value k, the k-FoldRegularCover problems
would be natural generalizations of GraphIso.
1.5. Three Properties. Let C be a class of connected multigraphs. By C/Γ we denote the class of all
regular quotients of graphs of C (note that C ⊆ C/Γ). For instance, when C is the class of planar graphs,
then the class C/Γ is, by Negami Theorem [52], the class of projective planar graphs. We define the following
three properties of C, for formal definitions see Section 2:
(P1) The classes C and C/Γ are closed under taking subgraphs and under replacing connected components
attached to 2-cuts by edges.
(P2) For a 3-connected graph G ∈ C, all semiregular subgroups Γ of Aut(G) can be computed in polynomial
time. Here by semiregularity, we mean that the action of Γ has no non-trivial stabilizers of the vertices.
(P3) Let G and H be 3-connected graphs of C/Γ, possibly with colored and directed edges, and the vertices

6

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

of G be equipped with lists. We can decide ListIso of G and H in polynomial time. (Where the
list-compatible isomorphism respects orientations and colors of edges.)
As we prove in Lemma 6.2, these three properties are tailored for the class of planar graphs. (The proof of
the property (P3) is non-trivial, following from [41].) The main reason to state (P1) to (P3) is explicitely to
make clear which properties of planar graphs are necessary for our algorithm.
Since ListIso is NP-complete in general, we also use the restricted version with only ColorIso to
highlight places where ListIso can be avoided:
(P3∗ ) Let G and H be 3-connected graphs of C/Γ, possibly with colored and directed edges, and the vertices
of G and H are colored. We can decide ColorIso of G and H in polynomial time.
1.6. The Meta-algorithm. This paper studies complexity of regular covering testing, based on our
structural results described in [26]. We establish the following algorithmic result:
Theorem 1.3. Let C be a class of graphs satisfying (P1) to (P3). There exists an FPT algorithm for
RegularCover for C-inputs G in time O∗ (2e(H)/2 ), where e(H) is the number of edges of H.
Since the assumptions (P1) to (P3) are satisfied for planar graphs (Lemma 6.2), we get Theorem 1.1.
Notice that if the input graph G is 3-connected, using our assumptions the RegularCover problem can be
trivially solved, by enumerating all its regular quotients and testing graph isomorphism with H. Babai [5]
proved that to solve graph isomorphism, it is sufficient to solve graph isomorphism for 3-connected graphs.
We wanted to generalize this result to regular covers, but handling 2-cuts is very complicated and we need
the assumptions (P2) and (P3).
We process the graph G by a series of reductions, replacing parts of the graph by edges, essentially
forgetting details of the graph. We end-up with a primitive graph which is either 3-connected, or very
simple (a cycle or K2 ). This very natural idea of reductions was first introduced in a seminal paper of
Trakhtenbrot [56] and further extended in [57, 37, 19, 59, 5]. The main difference is that these papers apply
the reduction only to 2-connected graphs, but in [26], we also reduce parts separated by 1-cuts. The reason
is that a regular quotient of a 2-connected graph might be only 1-connected, see Sections 3.1 and 4.1. Also,
we prove in [26] that no essential information of semiregular actions is lost during reductions.
In [26], we describe how regular covering behaves with respect to vertex 1-cuts and 2-cuts. Concerning
1-cuts, regular covering behaves non-trivially only on the central block of G, so they are easy to deal with.
But regular covering can behave highly complex on 2-cuts. In this paper, we build an algorithm based on
these structural results of [26]. When the reductions reach a 3-connected graph, the natural next step is to
compute all its quotients; there are polynomially many of them according to (P2).
What remains is the most difficult part: To test for each quotient whether it corresponds to H after
unrolling the reductions which is called expanding. The issue is that there may be exponentially many
different ways to expand the graph, all described in [26]. Therefore, we have to test in a clever way whether
it is possible to reach H. Our algorithm consists of several subroutines, most of which we can perform in
polynomial time. Only one subroutine (finding a certain “generalized matching”) we have not been able to
solve in polynomial time.
This slow subroutine can be avoided in some cases:
Corollary 1.4. If G is a 3-connected graph, if H is a 2-connected graph, or if k = |G|/|H| is odd,
then the meta-algorithm of Theorem 1.3 can be modified to run in polynomial time.
Corollary 1.5. Let C be a class of graphs satisfying (P1), (P2), and (P3∗ ). There exists an algorithm
listing for C-inputs G all their regular quotients, with a polynomial-time delay.
Theorem 1.2 implies that to solve the RegularCover problem in general, one has to work with both
graphs G and H from the beginning. Our algorithm starts only with G and tries to match its quotients to
H only in the end.
Outline. In Section 2, we introduce the formal notation used in this paper. In Section 3, we state key
structural properties of atoms, reductions and expansions from [26]. In Section 4, we use them to design the
meta-algorithm of Theorem 1.3. In Section 5, we describe more details concerning the only slow subroutine
of the meta-algorithm. Finally, in Section 6 we show that the class of planar graphs satisfies (P1) to (P3),
thus proving Theorem 1.1. In Conclusions, we describe open problems and possible extensions of our results.
2. Definitions and Preliminaries. In this paper, we work with an extended model of graph which
is formally described in [26]. A multigraph G is a pair (V (G), E(G)) where V (G) is a set of vertices and
E(G) is a multiset of edges. We denote |V (G)| by v(G) = |G| and |E(G)| by e(G). The graph can possibly

7

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

contain parallel edges and loops, and each loop at u is incident twice with the vertex u. Each edge e = uv
gives rise to two half-edges, one attached to u and the other to v. We denote by H(G) the collection of
all half-edges. We denote |H(G)| by h(G) and clearly h(G) = 2e(G). As quotients, we sometime obtain
graphs containing (standalone) half-edges (missing the opposite half-edges).1 Also, in the reductions, we
obtain pendant edges, each consisting of two half-edges, one attached to some vertex u, the other attached
to no vertex.
Unless the graph is K2 , we remove all vertices of degree 1 while keeping both half-edges. Assuming that
the original graph contains no pendant edges, this removal does not change the automorphism group and
existence of regular covering projections from G to H (when the removal is applied on both G and H). A
pendant edge attached to v is called a single pendant edge if it is the only pendant edge attached to v. Most
graphs in this paper are assumed to be connected.
We consider graphs with colored edges and also with three different edge types (directed edges, undirected
edges and a special type called halvable edges). It might seem strange to consider such general objects. But
when we apply reductions, we replace parts of the graph by edges and the colors encode isomorphism classes
of replaced parts. This allows the algorithm to work with smaller reduced graphs while preserving important
parts of the structure of the original large graph. So even if the input graphs G and H are simple, more
complicated multigraphs are naturally constructed.
We denote groups by capital Greek letters as for instance Γ. We use Sn , Cn , Dn and An to denote
symmetric groups, cyclic groups, dihedral groups and alternating groups, respectively.
2.1. Automorphisms and Groups. We state the definitions in a very general setting of multigraphs
and half-edges. An automorphism π is fully described by a permutation πh : H(G) → H(G) preserving edges
and incidences between half-edges and vertices. Thus, πh induces two permutations πv : V (G) → V (G)
and πe : E(G) → E(G) connected together by the very natural property πe (uv) = πv (u)πv (v) for every
uv ∈ E(G). In most of situations, we omit subscripts and simply use π(u) or π(uv). In addition, we require
that an automorphism preserves colors, edge types and orientation of directed edges.
Automorphism Groups. Let Aut(G) be the group of all automorphisms of G. The orbit [v] of a vertex
v ∈ V (G) in the action of Γ ≤ Aut(G) is the set of all vertices {π(v) | π ∈ Γ ≤ Aut(G)}, and the orbit [e]
of an edge e ∈ E(G) is defined similarly as {π(e) | π ∈ Γ ≤ Aut(G)}. The stabilizer Γx of x is the subgroup
of all automorphisms which fix x. An action is called semiregular if it has no non-trivial (i.e., non-identity)
stabilizers of both vertices and half-edges. Further, we require the stabilizer of an edge in a semiregular
action to be trivial, unless it is a halvable edge, when it may contain an involution transposing the two
half-edges. We say that a group is semiregular if the associated action is semiregular. More information on
permutation groups can be found in [54].
2.2. Coverings. A graph G covers a graph H (or G is a cover of H) if there exists a locally bijective
homomorphism p called a covering projection. A homomorphism p from G to H is given by a mapping
ph : H(G) → H(H) preserving edges and incidences between half-edges and vertices. It induces two
mappings pv : V (G) → V (H) and pe : E(G) → E(H) such that pe (uv) = pv (u)pv (v) for every uv ∈ E(G).
The property to be local bijective states that for every vertex u ∈ V (G) the mapping ph restricted to the
half-edges incident with u is a bijection. Figure 2.1 contains two examples of graph covers. We mostly omit
subscripts and just write p(u) or p(e).

w
u

u

v

p

w
w

u

w

v

v

w

u

v

v

w

v

p′

u

u
G

u
H

v

w

G′

Fig. 2.1. Two covers of H. The projections pv and p′v are written inside of the vertices, and the projections pe and p′e are
omitted. Notice that each loop is realized by having two neighbors labeled the same, and parallel edges are realized by having
multiple neighbors labeled the same. Also covering projections preserve degrees.
1 Half-edges

are sometimes also called darts or arcs while half-edges with free-ends are called semiedges.

8

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Fig. 2.2. The Hasse diagram of all quotients of the cube graph depicted in a geometric way. When semiregular actions
fix edges, the quotients contain half-edges. The quotients connected by bold edges are obtained by 180 degree rotations. The
quotients connected by dashed edges are obtained by reflections. The tetrahedron is obtained by the antipodal symmetry of the
cube, and its quotient is obtained by a 180 degree rotation with the axis going through the centers of two non-incident edges of
the tetrahedron.

A fiber over a vertex v ∈ V (H) is the set p−1 (v), i.e., the set of all vertices V (G) that are mapped to v,
and similarly for fibers over half-edges. From the standard assumption that both G and H are connected, it
follows that all fibers of p are of the same size. In other words, |G| = k|H| for some k ∈ N, which is the size
of each fiber, and we say that G is a k-fold cover of H.
Regular Coverings. We are going to consider coverings which are highly symmetrical, called regular
coverings. For example, in Fig. 2.1, the covering p is more symmetric than p′ . Let Γ be a semiregular
subgroup of Aut(G). It defines a graph G/Γ called a (regular) quotient of G as follows: The vertices of G/Γ
are the orbits of the action of Γ on V (G), the half-edges of G/Γ are the orbits of Γ on H(G). A vertex-orbit
[v] is incident with a half-edge-orbit [h] if and only if the vertices of [v] are incident with the half-edges of
[h]. (Because the action of Γ is semiregular, each vertex of [v] is incident with exactly one half-edge of [h],
so this is well defined.)
We naturally construct p : G → G/Γ by mapping the vertices to its vertex-orbits and half-edges to its
half-edge-orbits, and it is a |Γ|-fold regular covering. Concerning an edge e ∈ E(G), it is mapped to an edge
of G/Γ if the two half-edges belong to different half-edge-orbits of Γ. If both half-edges belong to the same
half-edge-orbits, it corresponds to a standalone half-edge of G/Γ.
For the graphs G and H of Fig. 2.1, we get H ∼
= C3 which “rotates the outer cycle by step
= G/Γ for Γ ∼
′
three”, while p is not a regular covering. As a further example, Fig. 2.2 geometrically depicts all regular
quotients of the cube graph.
2.3. Complexity of Regular Graph Coverings. We establish fundamental complexity properties
of regular covering. Our goal is to highlight similarities with the graph isomorphism problem.
Belonging to NP. The H-Cover problem clearly belongs to NP since one can just test in polynomial
time whether a given mapping is a locally bijective homomorphism. Not so obviously, the same holds for
RegularCover:
Lemma 2.1. The RegularCover problem belongs to NP.
Proof. By definition, G regularly covers H if and only if there exists a semiregular subgroup Γ of Aut(G)
such that G/Γ ∼
= H. As a certificate, we give k permutations, one for each element of Γ, and an isomorphism
between G/Γ and H. We check that these permutations define a group Γ acting semiregularly on G. The

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

9

G
G

G
G

G

H
G′

H′

Fig. 2.3. The graph G′ is constructed by k copies of G with attached universal vertices connected into a cycle while H ′ is
constructed by attaching a universal vertex with a loop to H.

given isomorphism allows to check that the constructed G/Γ is isomorphic to H. Clearly, this certificate is
polynomially large and can be verified in polynomial time.
One can prove even a stronger result:
Lemma 2.2. For a mapping p : G → H, we can test whether it is a regular covering projection in
polynomial time.
Proof. Testing whether p is a covering projection can clearly be done in polynomial time. It remains to
test regularity. Choose an arbitrary spanning tree T of H. Since p is a covering, then p−1 (T ) is a disjoint
union of k isomorphic copies T1 , . . . , Tk of T . We number the vertices of the fibers according to the spanning
trees, i.e., p−1 (v) = {v1 , . . . , vk } such that vi ∈ Ti . This induces a numbering of the half-edges of each
fiber over a half-edge of H(H), following the incidences between half-edges and vertices. For every half-edge
h∈
/ H(T ), we define the permutation σh of {1, . . . , k} taking i to j if there is a half-edge h′ ∈ p−1 (h) incident
with a vertex of Ti and paired with a half-edge incident with a vertex of Tj .
Let Θ be the group generated by all σh , where h ∈
/ H(T ). We assume that G is connected. By OrbitStabilizer Theorem, we have |Θ| = |Θv | · |[v]|, and from the connectivity, it follows that |[v]| = k. Therefore,
the action of Θ is regular if and only if |Θ| = k which can be checked in polynomial time.
The constructed permutations σh associated with p are known in the literature [31] as permutation
voltage assigments associated with p.
GI-hardness. When k = |G|/|H| = 1, the problem RegularCover exactly corresponds to GraphIso.
Let GI be the class of decision problems polynomial-time reducible to GraphIso. Bodlaender [12] proved
the following for general covers (and his reduction works for regular covers as well):
Lemma 2.3. For every fixed k, the k-FoldCover and k-FoldRegularCover problems are GI-hard.
Proof. For input graphs G and H of the graph isomorphism problem, we construct the graphs G′ and H ′
depicted in Fig. 2.3. The reduction works since the universal vertices in G′ must be mapped to the universal
vertex in H ′ (since covering projection preserves degrees). Therefore, G′ (regularly) covers H ′ if and only if
G∼
= H.
3. Atoms, Reduction and Expansion. In this section, we state definitions and structural results
from [26], describing behaviour of regular graph covers with respect to 1-cuts and 2-cuts in G. We also
prove new results concerning computational complexity of these techniques. In Section 3.1, we introduce
block-trees and describe behaviour of regular covering with respect to 1-cuts. In Section 3.2, we introduce
atoms which are inclusion-minimal parts of G with respect to 1-cuts and 2-cuts. In Section 3.3, we describe
the reduction which replaces atoms by colored edges, preserving the essential structure of G. In Section 3.4,
we consider quotients of reduced graphs and revert the reductions in them by expansions.
3.1. Block-trees and Central Blocks. The block-tree T of G is defined as follows. Consider all
articulations in G and all maximal 2-connected subgraphs which we call blocks (with bridge-edges and
pendant edges also counted as blocks). The block-tree T is the incidence graph between the articulations
and the blocks. For an example, see Fig. 3.1.
The Central Block. Recall that for a tree, its center is either the central vertex or the central pair of
vertices of a longest path, depending on the parity of its length. Every automorphism of a tree preserves its
center.
Lemma 3.1 ([26], Lemma 2.1). If G has a non-trivial semiregular automorphism, then G has a central
block.

10

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

G

T

Fig. 3.1. On the left, an example graph G with denoted blocks. On the right, the corresponding block-tree T is depicted,
rooted at the central block. The white vertices correspond to the articulations and the big black vertices correspond to the blocks.

In the following, we shall assume that T contains a central block C. We orient the edges of the blocktree T towards the central block; so the block-tree becomes rooted. A (rooted) subtree of the block-tree is
defined by any vertex different from the central block acting as root and by all its descendants. Let u be
an articulation contained in C. By Tu we denote the subtree of T defined by u and all its predecessors, and
let Gu be the graph induced by all vertices of the blocks of Tu . All semiregular subgroups of Aut(G) act
non-trivially and faithfully only on C:
Lemma 3.2 ([26], Lemma 2.2). Let Γ be a semiregular subgroup of Aut(G). If u and v are two
articulations of the central block and of the same orbit of Γ, then Gu ∼
= Gv . Moreover there is a unique
π ∈ Γ which maps Gu to Gv .
In the language of quotients, it means that G/Γ consists of C/Γ together with the graphs Gu attached
to C/Γ, one for each orbit of Γ.
Why Not Just 2-connected Graphs? Since the behaviour of regular covering with respect to 1-cuts in
G is very simple, a natural question follows: why do we not restrict ourselves to 2-connected graphs G? For
instance when solving graph isomorphism, it is sufficient to solve graph isomorphism of 2-connected graphs
and use it to find isomorphism of block-trees.
This is not possible for regular covering testing. The issue is that the quotient C/Γ might not be 2connected, so it may consists of many blocks and it is not easy to locate it in H. When H contains a subtree
of blocks isomorphic to Gu , it may correspond to Gu , or it may correspond to a quotient of a subgraph
of C/Γ, together with some other Gv attached. We use dynamic programming to deal with this in the
meta-algorithm, see Section 4.1. Therefore, we have to define 3-connected reduction for 1-cuts in G as well,
unlike in [56, 37, 19, 59, 5].
3.2. Atoms. Suppose that B is a block of G, in particular B is 2-connected. Two vertices u and v
form a 2-cut U = {u, v} if B \ U is disconnected. We say that a 2-cut U is non-trivial if deg(u) ≥ 3 and
deg(v) ≥ 3 in B.
Atoms are inclusion-minimal subgraphs with respect to 1-cuts and 2-cuts in G. We first define a set P
of subgraphs of G called parts which are candidates for atoms:
• A block part is a subgraph non-isomorphic to a pendant edge induced by the blocks of a subtree of
the block-tree.
• A proper part is a subgraph S of G defined by a non-trivial 2-cut U of a block B. The subgraph S
consists of a connected component K of G \ U together with u and v and all edges between {u, v}
and K. In addition, we require that S does not contain the central block; so it only contains some
blocks of the subtree of the block-tree rooted at B.
• A dipole part is any dipole defined as follows. Let u and v be two distinct vertices of degree at least
three joined by at least two parallel edges. Then the subgraph induced by u and v is called a dipole.
The inclusion-minimal elements of P are called atoms. We distinguish block atoms, proper atoms and dipoles
according to the type of the defining part. Block atoms are either stars of pendant edges called star block
atoms, or pendant blocks possibly with single pendant edges attached to them called non-star block atoms.
Each proper atom is a subgraph of a block, together with some single pendant edges attached to it. A dipole
part is by definition always inclusion-minimal, and therefore it is an atom. For an example, see Fig. 3.2.

11

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

block atoms

proper atoms

dipoles

Fig. 3.2. An example of a graph with denoted atoms. The white vertices belong to the boundary of some atom, possibly
several of them.

We use the topological notation to denote the boundary ∂A and the interior Å of an atom A. If A is a
dipole, we set ∂A = V (A). If A is a proper or block atom, we put ∂A equal to the set of vertices of A which
are incident with an edge not contained in A. For the interior, we use the standard topological definition
Å = A \ ∂A where we only remove the vertices ∂A, the edges adjacent to ∂A are kept in Å. Single pendant
edges of A are always attached to Å.
Note that |∂A| = 1 for a block atom A, and |∂A| = 2 for a proper atom or dipole A. The interior of a
dipole is a set of free edges. For a proper atom A, the vertices of ∂A are exactly the vertices {u, v} of the
non-trivial 2-cut used in the definition of proper parts, and they are never adjacent in A.
Lemma 3.3 ([26], Lemma 3.3). Let A and A′ be two different atoms. Then A ∩ A′ = ∂A ∩ ∂A′ .
Lemma 3.4 ([26], Lemma 3.8). Let A be an atom and let π ∈ Aut(G).
(a) The image π(A) is an atom isomorphic to A. Moreover π(∂A) = ∂π(A) and π(Å) = π̊(A), where
π̊(A) denotes the interior of π(A).
(b) If π(A) 6= A, then π(Å) ∩ Å = ∅.
(c) If π(A) 6= A, then π(A) ∩ A = ∂A ∩ ∂π(A).
Primitive Graphs. A graph is called primitive if it contains no atoms. The following lemma characterizing
primitive graphs can be alternatively obtained from the well-known theorem by Trakhtenbrot [56], see Fig. 3.3
for examples.2
Lemma 3.5 ([26], Lemma 3.4). Let G be a primitive graph. If G has a central block, then it is a
3-connected graph, a cycle Cn for n ≥ 2, or K2 , or can be obtained from the aforementioned graphs by
attaching single pendant edges to at least two vertices. If G has a central articulation, then it is K1 , possible
with a single pendant edge attached.
Lemma 3.6. If primitive graphs G and G′ belong to C satisfying (P3 ∗), then we can test G ∼
= G′ in
polynomial time.

u

B

B

B

Fig. 3.3. A primitive graph with a central block is either K2 , Cn , or a 3-connected graph, in all three cases with possible
single pendant edges attached to it.

2 We

consider K1 with an attached single pendant edge as a graph with a central articulation.

12

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Proof. In both graphs, we replace single pendant edges with colored vertices. If G and G′ are K1 , or
K2 , the problem is trivial. If they are cycles, we use the standard cycle isomorphism algorithms. If they are
3-connected, we test G ∼
= G′ using (P3∗ ).
Structure of Atoms. We call a graph essentially 3-connected if it is a 3-connected graph with possibly
single pendant edges attached to it. Similarly, a graph is called essentially a cycle if it is a cycle with possibly
single pendant edges attached to it. The structure of dipoles and star block atoms is clear. Non-star block
and proper atoms are either almost 3-connected, or very simple:
Lemma 3.7 ([26], Lemma 3.5). Every non-star block atom A is either K2 with an attached single pendant
edge, essentially a cycle, or essentially 3-connected.
Let A be a proper atom with ∂A = {u, v}. We define the extended proper atom A+ as A with the
additional edge uv. Notice that the property (P1) ensures that A+ belongs to the class C.
Lemma 3.8 ([26], Lemma 3.6). For every proper atoms A, the extended proper atom A+ is either
essentially a cycle, or essentially 3-connected.
Two atoms A and A′ are isomorphic if there exists an isomorphism which maps ∂A to ∂A′ .
Lemma 3.9. For every atoms A and A′ of a graph G belonging to C satisfying (P1) and (P3 ∗), we can
test A ∼
= A′ in polynomial time.
Proof. If both A and A′ are dipoles and star block atoms, we can test A ∼
= A′ trivially in polynomial
time. If they are non-star block atoms, by Lemma 3.7 they are either K2 with attached single pendant edge,
or essentially a cycle, or essentially 3-connected. The first two possibilities can be solved trivially, so we
assume that A and A′ are essentially 3-connected. Let B and B ′ be the 3-connected graph created from
A and A′ by removing pendant edges, where existence of pendant edges is coded by colors of V (B) and
V (B ′ ), and we further color ∂B and ∂B ′ by a special color. We have A ∼
= A′ if and only if there exists
′
a color-preserving isomorphism between B and B which can be tested using (P3∗ ). When A and A′ are
proper atoms, we proceed similarly on extended proper atoms, using Lemma 3.8.
Symmetry Types of Atoms. We distinguish three symmetry types of atoms, and in reductions, we replace
atoms by edges carrying their types. Therefore we work with multigraphs with three edge types: halvable
edges, undirected edges and directed edges. We consider only the automorphisms which preserve these edge
types and of course the orientation of directed edges. For an atom A, we denote by Aut(A) the setwise
stabilizer of ∂A.
Let A be a proper atom or dipole with ∂A = {u, v}. We distinguish the following three symmetry types,
depicted in Fig. 3.4:
• The halvable atom. There exists a semiregular involutory automorphism τ ∈ Aut(A) which exchanges u and v. More precisely, the automorphism τ fixes no vertices and no directed and undirected
edges, but some halvable edges may be fixed.
• The symmetric atom. The atom is not halvable, but there exists an automorphism in Aut(A) which
exchanges u and v.
• The asymmetric atom. The atom is neither halvable, nor symmetric.
If A is a block atom, then it is by definition symmetric.
Lemma 3.10. For a dipole A, we can determine its symmetry type in polynomial time.
Proof. The type depends only on the quantity of distinguished types of the parallel edges. We have
directed edges from u to v, directed edges from v to u, undirected edges and halvable edges. We call a dipole
balanced if the number of directed edges in the both directions is the same. The dipole is halvable if and

u

v

halvable atom
u

v

u

v

symmetric atom
u

v

u

v

asymmetric atom
u

v

Fig. 3.4. The three types of atoms and the corresponding edge types which we use in the reduction. We denote halvable
edges by small circles in the middle.

13

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

u

v

u

v

A+

c
−→

u

v

B

B

c
Fig. 3.5. For the depicted atom A, we test using (P3 ∗) whether B −→
B. In this case yes, so A is either symmetric, or
halvable.

only if it is balanced and has an even number of undirected edges. The dipole is symmetric if and only if
it is balanced and has an odd number of undirected edges. The dipole is asymmetric if and only if it is
unbalanced. This clearly can be tested in polynomial time.
Lemma 3.11. For a proper atom A of C satisfying (P1), (P2), and (P3 ∗), we can determine its symmetry
type in polynomial time.
Proof. Let ∂A = {u, v}. By Lemma 3.8, A+ is either essentially a cycle (which is easy to deal with), or
an essentially 3-connected graph. Let B be the 3-connected graph created from A+ by removing pendant
edges, where existence of pendant edges is coded by colors of V (B). By (P1), both A+ and B belong to C.
We apply (P3∗ ) on two copies of B. In one copy, we color u by a special color, and v by another special
color. In the other copy, we swap the colors of u and v. Using (P3∗ ), we check whether there exists a
color-preserving automorphism which exchanges u and v; see Fig. 3.5. If not, then A is asymmetric. If yes,
we check whether A is symmetric or halvable.
Using (P2), we generate polynomially many semiregular involutions of order two acting on B. For
each semiregular involution, we check whether it transposes u to v, and whether it preserves the colors of
V (B) coding pendant edges. If such a semiregular involution exists, then A is halvable, otherwise it is just
symmetric.
Regular Projections and Quotients of Atoms. Let Γ be a semiregular subgroup of Aut(G), which
defines a regular covering projection p : G → G/Γ. For a proper atom or a dipole A with ∂A = {u, v}, we
get three possible types of projection p|A ; see Fig. 3.6:
• An edge-projection. The atom A is preserved in G/Γ, meaning p(A) ∼
= A. Notice that p(A) may
just be a subgraph of G/Γ, not induced. For instance, it can happen that p(u)p(v) ∈ E(G/Γ) while
uv ∈
/ E(G).
• A loop-projection. The interior Å is preserved and the vertices u and v are identified, i.e., p(Å) ∼
= Å
and p(u) = p(v).
• A half-projection. There exists an involutory permutation π in Γ which exchanges u and v and
preserves A. The projection p(A) is a halved atom A. This can happen only when A is a halvable
atom. In particular, the covering projection p is a 2k-fold covering.
Lemma 3.12 ([26], Lemma 3.9). For an atom A and a regular covering projection p, we have p|A either
an edge-projection, a loop-projection, or a half-projection. Moreover, for a block atom we have exclusively
an edge-projection.
So we get three types of quotients p(A) of A. For an edge-projection, we call this quotient an edgequotient, for a loop-projection, we call it a loop-quotient, and for a half-projection, we call it a half-quotient.
The following lemma allows to say “the” edge- and “the” loop-quotient of an atom.
Lemma 3.13 ([26], Lemma 3.9). For every atom A, there is the unique edge-quotient and the unique
loop-quotient up to isomorphism.

edge-projection
p(A)
p(u)

loop-projection
p(A)

p(v)

p(u) = p(v)

half-projection
p(A)
p(u) = p(v)

Fig. 3.6. How can p(A) look in G/Γ, for three types of projection.

14

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Fig. 3.7. Assuming that quotients can contain half-edges, the depicted dipole has four non-isomorphic half-quotients.

For half-quotients, this uniqueness does not hold. First, an atom A with ∂A = {u, v} has to be halvable to
admit a half-quotient. Then each half-quotient is determined by an involutory automorphism τ exchanging
u and v; here τ is the restriction of π from the definition of a half-projection. First, several different
automorphisms τ may define equivalent covering projections p of A, so p(A) is an isomorphic half-quotient.
On the other hand, different automorphisms τ may define non-equivalent covering projections p of A, so
they give non-isomorphic half-quotients p(A); see Fig. 3.7. For a proper atom, we can bound the number of
non-isomorphic half-quotients by the number of different semiregular involutions of 3-connected graphs.
Lemma 3.14. Let A be a proper atom of C satisfying (P1) and (P2). Then there are polynomially many
non-isomorphic half-quotients of A which can be computed in polynomial time.
Proof. By Lemma 3.8, A+ is either essentially a cycle (where it holds trivially), or it is an essentially
3-connected graph. We construct B + from A+ be replacing pendant edges with colored vertices, by (P1)
both A+ and B + belong to C. According to (P2), the number of different semiregular subgroups of order
two is polynomial in the size of B + . Each half-quotient is defined by one of these semiregular involutions
which fixes the edge uv, transposes u and v, and preserves colors.
3.3. Reduction. The reduction produces a reduction series of graphs G = G0 , . . . , Gr . It produces
graphs with colored edges and with three edge types: halvable, undirected and directed. We note that the
results built in Section 3.2 transfers to colored graphs and colored atoms without any problems.
To construct Gi+1 from Gi , we find the collection of all atoms A of Gi , together with isomorphism
classes such that A and A′ belong to the same class if and only if A ∼
= A′ . To each isomorphism class, we
assign one new color not yet used in the graphs G0 , . . . , Gi . We replace the atoms A in Gi by edges of colors
of the corresponding isomorphism classes as follows.
For each block atom A with ∂A = {u}, we replace it by a pendant edge of some color based at
u. For each proper atom or dipole A with ∂A = {u, v}, we replace it by a new edge uv which is halvable/undirected/directed when A is halvable/symmetric/asymmetric, respectively. Naturally, for each isomorphism class of asymmetric atom, we consistently choose an arbitrary orientation of the directed edges
replacing these atoms. For an example of the reduction, see Fig. 3.8. By Lemma 3.3, the replaced the
interiors of the atoms of A are pairwise disjoint, so the reduction is well defined.
The reduction series stops in the step r when Gr is a primitive graph. For every graph G, the reduction
series corresponds to the reduction tree which is a rooted tree defined as follows. The root is the primitive
graph Gr , and the other nodes are the atoms obtained during the reductions. If a node contains a colored
edge, it has the corresponding atom as a child. Therefore, the leaves are the atoms of G0 , after removing

red.

G0

G1

Fig. 3.8. On the left, we have a graph G0 with three isomorphism classes of atoms. The dipoles are halvable, the block
atoms are symmetric and the proper atoms are asymmetric. We reduce G0 to G1 which is an eight cycle with single pendant
edges, with four black halvable edges replacing the dipoles, eight gray undirected edges replacing the block atoms, and four white
directed edges replacing the proper atoms. The reduction series ends with G1 since it is primitive.

15

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

G1

Fig. 3.9. The reduction tree for the reduction series in Fig. 3.8. The root is the primitive graph G1 and each leaf
corresponds to one atom of G0 .

them, the new leaves are the atoms of G1 , and so on. For an example, see Fig. 3.9. It is proved in [26, 42]
that the reduction series and the reduction tree captures Aut(G).
Lemma 3.15. If a graph G belongs to C satisfying (P1), (P2) and (P3 ∗), then the reductions series
G = G0 , . . . , Gr and the reduction tree can be computed in polynomial time.
Proof. To compute Gi+1 from Gi , we find all atoms A in Gi and A′ in G′i , compute their isomorphism
classes by Lemma 3.9 and assign new colors to them. By Lemmas 3.10 and 3.11, we compute symmetry
types of these atoms. We end up with a primitive graph Gr containing the atoms. The reduction tree can
be easily constructed and the algorithm runs in polynomial time.
The following is the approach invented by Babai [5]:
Lemma 3.16 ([5]). If graphs G and G′ belong to C satisfying (P1) and (P3 ∗), we can test G ∼
= G′ in
polynomial time.
Proof. Using Lemma 3.15, we simultaneously apply reduction series on both G and G′ in polynomial
time, using identical colors for isomorphic atoms in Gi and G′i . (We do not need to distinguish halvable and
symmetric atoms, so (P2) is not needed.) We end up with two primitive graphs Gr and G′r and we test their
isomorphism using Lemma 3.6. Alternatively, we can compute both reduction trees and apply the standard
tree isomorphism of graph-labeled trees.
In general, the reduction series does not have to preserve the central block, and the atoms A of
G0 , . . . , Gr−1 has to be defined with respect to one chosen block which is preserved. On the other hand,
by Lemma 3.1, if the RegularCover problem is non-trivial, then G contains the central block which is

red.

red.

G0 /Γ0

G1 /Γ1

G0 /Γ′0

G1 /Γ′1

Fig. 3.10. An example of two quotients G0 /Γ0 and G0 /Γ′0 of the graph G0 from Fig. 3.8 with the corresponding quotients
of the reduced graph G1 .

16

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

reduction

−→ H1

···

−→

Γ1

Gi

−→ Gi+1 −→

Hi

−→ Hi+1 −→

Γi+1

Γi

−→

···

−→

···

−→ Gr
−→

−→

H0

Γ0

−→

−→

−→ G1

−→

G0
−→

G=

Γr

···

−→ Hr

replacement of quotients of atoms by edges, loops and half-edges
Fig. 3.11. The graph Hi+1 is constructed from Hi by replacing the projections of atoms in Hi by the corresponding
projections of the edges replacing the atoms.

preserved by the reduction series:
Lemma 3.17 ([26], Lemma 4.1). Let G admit a non-trivial semiregular automorphism π. Then each
Gi+1 has a central block which is obtained from the central block of Gi by replacing its atoms by colored
edges.
Quotient Reduction. Let G0 , . . . , Gr be the reduction series of G and let Γ0 be a semiregular subgroup
of Aut(G0 ). By Lemma 3.4, we argue that Γ0 uniquely determines semiregular subgroups Γ1 , . . . , Γr of
Aut(G1 ), . . . , Aut(Gr ). Each element π ∈ Γi somehow permutes atoms A of Gi and somehow permutes the
rest of Gi . The reduction constructs Gi+1 from Gi by replacing A with colored edges. Therefore, π ′ ∈ Γi+1
corresponding to π can be defined in the following way. It permutes the colored edges in the same way as π
permutes the respective atoms of A, while π ′ is equal to π on the rest of the graph. The mapping π 7→ π ′
defines the reduction epimorphism Φi : Aut(Gi ) → Aut(Gi+1 ); see [26], Proposition 4.1.
Let Hi = Gi /Γi be the quotients with preserved colors and types of edges, and let pi be the corresponding
covering projection from Gi to Hi . Recall that Hi can contain edges, loops and half-edges; depending on the
action of Γi on the half-edges corresponding to the edges of Gi . We investigate relation between Hi = Gi /Γi
and Hi+1 = Gi+1 /Γi+1 .
Let A be an atom of Gi represented by a colored edge e in Gi+1 . By Lemma 3.12, pi |A can have three
types of projections. It is easy to see that pi+1 (e) corresponds to an edge (for a block atom, to a pendant
edge) for the edge-projection, to a loop for the loop-projection and to a half-edge for a half-projection. This
explains the names of the quotients pi (A) as the edge-quotient, the loop-quotient and a half-quotient. See
Fig. 3.10 for examples and see the diagram in Fig. 3.11.
3.4. Expansion. We want to understand the expansion of quotients, corresponding to the diagram in
Fig. 3.12. Suppose that Γr is a semiregular subgroup of Aut(Gr ), defining the quotient Hr = Gr /Γr . The
expansion constructs a series of semiregular subgroups Γr , . . . , Γ0 defining expanded quotients Hi = Gi /Γi .
Unfortunately, the expansion is non-deterministic which means that the expanded quotients
Hr−1 , . . . , H0 are not uniquely determined. Recall Lemma 3.12 and Fig. 3.6. The following characterization
of all expanded quotients is the main result of [26]:
Theorem 3.18 ([26], Theorem 1.2). Let Gi+1 be a reduction of Gi . Every quotient Hi of Gi can
be constructed from some quotient Hi+1 of Gi+1 by replacing each edge, loop and half-edge of Hi+1 by the
subgraph corresponding to the edge-, the loop-, or a half-quotient of an atom of Gi , respectively.

reduction

←− H1

···

−→

Γ1

Gi

−→ Gi+1 −→

Hi

←− Hi+1 ←−

Γi+1

Γi

←−

···

←−

···

−→ Gr
−→

−→

H0

Γ0

−→

−→

−→ G1

−→

G0
−→

G=

Γr

···

←− Hr

expansion
Fig. 3.12. The expansion constructs the graph Hi from Hi+1 by replacing the edges, loops and half-edges corresponding
to quotients of atoms in Hi by the edge-, the loop- and some choices of half-quotients.

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

17

Fig. 3.13. An example of a dipole with four non-isomorphic half-quotiens.

By Lemma 3.13, the edge and loop-quotients are uniquely determined. The expansion is nondeterministic since there might be many non-isomorphic half-quotients, leading to different graphs Hi . For
instance, suppose that Hi+1 contains a half-edge corresponding to the dipole from Fig. 3.13. To construct
Hi , we replace this half-edge by one of the four possible half-quotients of this dipole.
Corollary 3.19 ([26], Corollary 4.8). If Hi+1 contains no half-edge, then Hi is uniquely determined.
Thus, for an odd order of Γr , the quotient Hr uniquely determines H0 .
Half-quotients of Dipoles. Dipoles with colored edges may admit exponentially many non-isomorphic
half-quotients; see Fig. 3.13. Therefore, if Hi+1 contains a half-edge corresponding to a half-quotient of a
dipole in Hi , the number of non-isomorphic expansions Hi of Hi+1 can be exponential in the size difference
of Hi and Hi+1 .
Lemma 3.20 ([26], Lemma 4.9). Let A be a dipole with colored edges. Then the number of pairwise
non-isomorphic half-quotients is bounded by 2⌊e(A)/2⌋ and this bound is achieved.
For the purpose of Section 4, we describe the structure of all quotients of a dipole. Each is constructed
from an involutory semiregular automorphisms τ acting on Å. If ∂A = {u, v}, the half-quotient A/ hτ i
consists of a vertex p(u) with several loops and half-edges attached at u. Since τ preserves the color classes
and edge types, it acts indepedently on each color class and type of edges.
On each color class of the non-halvable edges of A, τ acts as a fixed-point free involution. The undirected
edges have to be paired by τ together. Each directed edge has to be paired with a directed edge of the opposite
direction and the same color. In the quotient A/ hτ i, we have no freedom: we get a (directed) loop for each
such pair.
On each color class of halvable edges of A, τ acts as an arbitrary semiregular involution. An edge e fixed
in τ is mapped into a half-edge of the given color in A/ hτ i. If τ maps e to e′ 6= e, then we get a loop in
A/ hτ i. The resulting half-quotient is therefore determined by the numbers h of fixed edges and the numbers
ℓ of two-cycles for each color class of halvable edges of size m such that h + 2ℓ = m.
The Block Structure of Quotients. Last, we describe how the block structure changes during expansions.
A block atom A of Gi is always projected by an edge-projection, so it corresponds to a block atom of Hi .
Suppose that A is a proper atom or a dipole with ∂A = {u, v}. For an edge-projection, we get p(u) 6= p(v),
and p(A) is isomorphic to an atom in Hi .
For a loop- or half-projection, we get p(u) = p(v) and p(u) is an articulation of Hi . If A is a dipole, then
p(A) is a pendant star of half-edges and loops attached to p(u). By Lemma 3.8, if A is a proper atom, then
p(A) is either a path ending with a half-edge and with attached single pendant edges (when A+ is essentially
a cycle), or a pendant block with attached single pendant edges and half-edges (when A+ is essentially
3-connected). (The reason is that the fiber of an articulation in a 2-fold cover is a 2-cut.)
Lemma 3.21 ([26], Lemma 4.10). The block structure of Hi+1 is preserved in Hi , possibly with some
new subtrees of blocks attached.
4. Meta-algorithm. In this section, we establish the meta-algorithm from Theorem 1.3, solving RegularCover for G belonging to C satisfying (P1) to (P3) in time O∗ (2e(H)/2 ).
Let k = |G|/|H|, and we assume that k ≥ 2. (If k is not an integer, then clearly G does not cover H. If
k = 1, then it is equivalent to the graph isomorphism problem and we can test it using Lemma 3.16.) The
algorithm consists of the following major parts:
1. Reduction Part: We construct the reduction series for G = G0 , . . . , Gr terminating with the unique
primitive graph Gr . Throughout the reduction the central block is preserved, otherwise according
to Lemma 3.17 there exists no semiregular automorphism of G and we output “no”. According to
(P1), the reduction preserves the class C, and also every atom belongs to C.
2. Quotient Part: Using (P2), we construct the list of all subgroups Γr of Aut(Gr ) of the order k acting
semiregularly on Gr . The number of subgroups in the list is polynomially large by (P2).

18

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

edge-projection

loop-projection

half-projection
?

G

G

G

H

Fig. 4.1. For a pendant block of H, there are three possible preimages in G. It could be a block atom mapped by the
edge-projection, or a proper atom mapped by the loop-projection, or another proper atom mapped by a half-projection (where
the half-quotient is created by 180◦ rotation τ ).

3. Expansion Part: For each Γr in the list, we compute Hr = Gr /Γr . We say that a graph Hr is expandable if there exists a sequence of extensions repeatedly applying Theorem 3.18 which constructs
H0 isomorphic to H. We test the expandability of Hr using dynamic programming while using (P3).
It remains to explain details of Expansion Part, and prove the correctness of the algorithm.
Outline. In Section 4.1, we give an overview of Expansion Part. In Section 4.2, we describe a catalog which
stores all atoms and their quotients discovered during reductions. In Section 4.3, we describe reductions
with lists, used in expandibility testing. Last, in Section 4.4, we conclude with a proof of Theorem 1.3.
4.1. Overview of Testing Expandability. In this section, we explain how to test expandability of
Hr . We start by illustrating the fundamental difficulty, for simplicity on pendant blocks. Suppose that H
has a pendant block as in Fig. 4.1. From the local information, there is no way to know whether this block
corresponds in G to the edge-quotient of a block atom, or to the loop-quotients of some proper atoms, or to
half-quotients of some other proper atoms. It can easily happen that the all these atoms appear in G. So
without exploiting some additional information from H, there is no way to know what is the preimage of
this pendant block.
In our approach, we revert the problem of expandability of Hr by reducing H towards Hr . But since it
is not clear which atoms of H correspond to which parts of G, we do not decide it during the reductions,
instead we just remember lists of all possibilities. The dynamic programming deals with these lists and
computes further lists for larger parts of H. Figure 4.2 illustrates the overview of our algorithm.
Reductions of Quotients and Cores. Notice that Hr might not be primitive; see Fig. 4.3 for an example.
It would be difficult to match it to a reduction series in H, so in Step 3, we further reduce Hr to a primitive
graph Hs .
We define atoms in the quotient graphs similarly as in Section 3.2 with only one difference. We choose one
arbitrary block/articulation called the core in Hr ; for instance, we can choose the central block/articulation.
The core plays the role of the central block in the definition of parts and atoms. Also, in the definition
we consider half-edges and loops as pendant edges, so they do not form block atoms. We proceed with the
reductions in Hr further till we obtain a primitive quotient graph Hs , for some s ≥ r; see Fig. 4.4.
Let H0 , . . . , Hs−1 be the graphs obtained by an expansion series of Hs using Theorem 3.18.
Lemma 4.1. The graph Hs is expandable to H, if and only if Hr is expandable to H.

Step 1: reduction

−→

H0

←− H1

Γ0

−→

···

−→ Gr

Γ1

Γr

←−

···

←− Hr

Step 2: choose semiregular Γr ≤ Aut(G)
Step 3 further reduction
−→ Hr+1 −→ · · · −→ H
s
←−
←−
←−

Step 7: compute the expansion from the isomorphism
H = R0

−→ R1

−→

Step 4: choose core in H

···

−→

Ri

−→ Ri+1 −→

···

Step 6:

−→

−→ G1

−→

G0
−→

G=

−→

Rt

L

?

Step 5: reduction with lists

Fig. 4.2. The metaalgorithm proceeds in the following seven steps. We iterate over all possible choices in Steps 2 and 4.

19

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

Γr

Hr = Gr /Γr

Gr

Fig. 4.3. A primitive graph Gr which is 3-connected. Let Γr be the semiregular subgroup of Aut(Gr ) generated by a 120◦
rotation. It defines the quotient Hr = Gr /Γr which is not primitive (contains articulations and 2-cuts).

Proof. It follows from the fact that the graphs Hs−1 , . . . , Hr are uniquelly determined, since no half-edges
are expanded till Hr .
Lemma 4.2. If Hs is expandable to H, then the core of Hs is expanded to some block or articulation of
H.
Proof. The graph Hs consists of the core together with some pendant edges, loops and half-edges. By
Lemma 3.21, the core is preserved as an articulation/block in all graphs Hs , . . . , H0 . The core can be only
changed by replacing of its colored edges by edge-quotients. Since Hs is expandable to H0 , the expanded
core is isomorphic to some block or articulation of H.
In Step 4, we test all possible positions of the core in H. (We have O(n) possibilities, so we run the
dynamic programming algorithm multiple times.) In what follows, we have the core fixed in H as well.
In Step 5, we apply on H reductions with lists, described in Section 4.3. In Step 6, we test whether
some choices from these lists are compatible with the graph Hs .
4.2. Catalog of Atoms. During the reduction phase of the algorithm, we construct the following
catalog of atoms forming a database of all discovered atoms. These atoms arise in three ways: atoms of
G0 , . . . , Gr−1 , atoms in half-quotients of these atoms, and atoms in the reductions of the quotients Hr =
Gr /Γr . We are not very concerned with a specific implementation of the algorithm, so the purpose of this
catalog is to simplify description.
For each isomorphism class of atoms represented by an atom A, we store the following information in
the catalog:
• The atom A.

red.

H1

red.

H2

red.

H3

H4

Fig. 4.4. The graph H1 is one quotient of G1 from Fig. 3.8. We further reduce it to H3 with respect to the core block
depicted in gray. Notice that H1 and H2 only contain block atoms.

20

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

• The corresponding colored edge of a given type representing the atom in the reduction.
• If A is an atom of G0 , . . . , Gr−1 , the unique edge- and loop-quotients of A and information about
its half-quotients.
For an overview of adding an atom A into the catalog, see Algorithm 1.
Storing Star Block Atoms. Let A be a star block atom. We store it in the catalog partially expanded
which works as follows. By the definition, A consists of a vertex with attached edges, loops and half-edges.
If some edge corresponds to a star block atom S, we replace it with the edges of S. Similarly, if some loop
corresponds to the loop-quotient Q of a dipole D, we replace it by the loops of Q. We repeat this till all
pendant edges of A correspond to block atoms and all loops of A correspond to loop-quotients of proper
atoms. On the other hand, the half-edges of A may correspond to half-quotients of both proper atoms and
dipoles.
Storing Dipoles. Let A be a dipole in G0 , . . . , Gr−1 . By Lemma 3.20, it can have exponentially many
non-isomorphic half-quotients. On the other hand, they are well described in Section 3.4, so we can generate
all of them from the dipole when needed.
We store this dipole A in the catalog partially expanded which works as follows. Almost all edges of A
correspond to proper atoms, while at most one edge corresponds to a dipole D. (At most one since from the
definition, a dipole D with ∂D = {u, v} consists of all edges between u and v.) If one edge corresponds to
D, we replace it in A with the edges of the dipole D. And if one of these edges of D again correspond to
some dipole D′ , we proceed further with the expansion.
Notice that by the definition of the reduction, all colored edges of D have different colors than the edges
Algorithm 1 The subroutine for adding an atom into the catalog
Require: An atom A.
Ensure: If A is not contained in the catalog, then it is added. A colored halvable/undirected/directed edge
corresponding to A is given.

10:
11:

if A is a star block atom then
while A contains a pendant edge e′ of a star block atom S do
Replace e′ with the edges of S.
while A contains a loop e′ of the loop-quotient of a dipole D do
Replace e′ with the loops of the loop-quotient of D.
if A is a dipole then
while A contains an edge e′ corresponding to a dipole D do
Replace e′ with the edges of D.
We test whether A is contained in the catalog using Lemma 4.4.
if A is contained in the catalog then
return The corresponding colored edge representing A.

12:
13:

We determine the symmetry type of A using Lemmas 3.10 and 3.11.
We assign an edge e of a new color of the corresponding type to A.

14:
15:

if A is an atom of G0 , . . . , Gr . then
We compute the edge-quotient of A and the loop-quotient of A (if A is not a block atom).
if A is a dipole consisting of exactly two halvable edges of the same color then
We add the half-quotient of A with one loop to the list of half-quotients.

1:
2:
3:
4:
5:
6:
7:
8:
9:

16:
17:
18:
19:
20:
21:
22:
23:
24:

if A is a halvable proper atom then
We compute all half-quotients Q of A by Lemma 3.14.
for each half-quotient Q do
Apply the reduction series on Q with respect to the block containing ∂Q, constructing a primitive
graph Q′ .
Add all detected atoms to the catalog and replace them by the corresponding colored edges.
Add Q′ to the catalog, as a half-quotient of A.
return The assigned colored edge e corresponding to A.

21

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

hτ i

red.

red.

Q = A/ hτ i

A

red.
Q′
Fig. 4.5. A proper atom A with a half-quotient Q generated by 180◦ rotation τ . A reduction series is applied on Q which
adds further atoms to the catalog and the primitive graph Q′ .

of A. Therefore the half-quotients of the original dipole A are exactly the same as the half-quotients of
the partially expanded dipole A. The reason for this expansion is that every half-quotient of the partially
expanded dipole A consists of loops and half-edges attached to one vertex, where each loop and each half-edge
is expanded into one block (with attached single pendant edges, half-edges and loops).
Further, if a halvable dipole A consists of exactly two edges of the same color, we compute its halfquotient consisting of just the single loop attached, and we add this quotient to the catalog. The reason is
that this quotient behaves exactly as the loop-quotient of some proper atom.
Storing Proper Atoms. If A is not a dipole, we compute the list of all its pairwise non-isomorphic halfquotients, and store them in the catalog in the following way. A half-quotient Q of A might not be primitive.
Therefore, we apply a reduction series on Q, and add all atoms discovered by the reduction to the catalog.
(We do not compute their half-quotients. They are never realized unless these atoms are directly found in G
as well.) When the reduction series finishes, this half-quotient is reduced to a primitive graph Q′ . Naturally,
the block containing ∂Q, being a single vertex of the half-quotient, behaves like the central block in the
definition of atoms, i.e., it is never reduced. The reduced half-quotient Q′ is either essentially 3-connected,
a cycle with attached single pendant edges, or K2 with a single pendant edge or half-edge attached. See
Fig. 4.5 for an example.
Total Size of Catalog. Next, we prove that the catalog is not too large.
Lemma 4.3. Assuming (P2), the catalog contains polynomially many atoms and half-quotients.
Proof. First we deal with the number of atoms in G0 , . . . , Gr . Notice that by replacing an interior of an
atom, the total number of vertices and edges is decreased; the interiors of atoms in each Gi contain at least
two vertices and edges in total and are pairwise disjoint (see Lemma 3.3). Thus we add a linear number of
atoms of G0 , . . . , Gr to the catalog, of total linear size.
By (P2), there are polynomially many possible quotients Hr , in each we encounter linearly many atoms
when reducing to Hs . So we add polynomially many atoms to the catalog.
By (P2), each proper atom A has polynomially many half-quotients, for different semiregular involutions
of Aut(A). So, we have in total polynomially many half-quotients, each containing at most linearly many
atoms in its reduction series. And by Lemma 3.13 we have the unique edge- and loop-quotient. So again,
the total number of atoms and quotients added to the catalog is polynomial.
Catalog Queries. Throughout the algorithm, we repeatedly ask queries whether some atom or some of its
quotients is contained in the catalog, and if so, we retrieve the corresponding colored edge/loop/half-edge.
Lemma 4.4. Assuming (P3 ∗), each catalog query can be answered in polynomial time.
Proof. By Lemma 4.3, we need to test graph isomorphism for the input atom/quotient and polynomially
many atoms/quotients in the catalog. If the input is an atom of an edge-quotient, we use Lemma 3.9. If it
is a loop- or a half-quotient, then it is a primitive graph and we use Lemma 3.6.
4.3. Reductions with Lists. In this section, we describe Steps 5 and 6 of the diagram in Fig. 4.2.
By Lemma 4.1, we need to test whether Hs is expandible to H. We approach this in the opposite way,
by applying a reduction series on H with respect to the core defining H0 , . . . , Ht . As already discussed in

22

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

red.

? x

L(x) =

n

,

,

o

R1

R0

Fig. 4.6. Let x be the pendant element corresponding to the pendant block of H depicted in Fig. 4.1. Then L(x) contains
three different members if all three atoms depicted in Fig. 4.1 are contained in the catalog.

Section 4.1, we do not know which parts of G project to different parts of H. Therefore each Hi is a set
of graphs, and Ht is a set of primitive graphs. We then determine expandability of Hs by testing whether
Hs ∈ Ht .
Since each set Hi can contain a huge number of graphs, we represent it implicitly in the following
manner. Each Hi is represented by one graph Ri with some colored edges and with so-called pendant
elements attached to some vertices.
Pendant Elements with Lists. A pendant element x in Ri corresponds to a block atom in Rj for some
j < i, which is reduced in Rj+1 . When pendant elements are fully expanded, they correspond to block part
of H with pairwise disjoint interiors. We use the name pendant element since it may represent a pendant
edge of some color, several loops of some other colors, and several half-edges of some other colors.
Each pendant element x is equipped with a list L(x) whose members are possible realizations of the
corresponding block atom by the quotients from the catalog. Each graph of Hi is created for Ri by replacing
the pendant elements by some choices of edges, loops and half-edges from their lists. The list L(x) of a
pendant element x contains an edge/loop/half-edge if and only if it is possible to expand this edge/loop/halfedge to the graph isomorphic to the block part corresponding to x. For an example, see Fig. 4.6. According
to Lemma 4.3, we have polynomially many atoms, and so the size of each list is polynomial in size.
Lemma 4.5. Each list L(x) contains at most one edge. Further, if two lists share an edge or a loop,
their pendant elements correspond to isomorphic block parts in H.
Proof. Two atoms have the isomorphic edge-quotients if and only if they are isomorphic. Therefore each
list L(x) contains at most one edge.
If a pendant element x is fully expanded, it corresponds to one block part of H. Suppose that an edgeor a loop-quotient belongs to L(x). If it is fully expanded, then it has to be isomorphic to this block part.
But according to Lemma 3.13, the expansions of edge- and loop-quotients are deterministic since half-edges
are never encountered. Therefore the corresponding block part in H is uniquely determined.
One list may contain several loops, for which identifying of the vertices of the boundaries constructs

A1

A2

A3
n

o
?

n

,

,

o

n

o
?

n

o

Fig. 4.7. Two block atoms corresponding to pendant elements with depicted lists. On the left, the list has the loops
corresponding to A1 and A2 and the half-edge corresponding to A3 . On the right, the list only contains the half-edge of A3 .

23

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

hτ1 i
D1

hτ2 i

≈
D1 / hτ1 i

D2 / hτ2 i

D2

Fig. 4.8. An example of two dipoles D1 and D2 having isomorphic half-quotients. Consider the atoms A1 and A3 from
Fig. 4.7, for which the loop-quotient of A1 is isomorphic to a half-quotient of A3 . Let D1 consist of four edges corresponding to
A1 and let D2 consist of two edges corresponding to A3 . Then the half-quotient D1 / hτ1 i can be expanded to a graph isomorphic
to an expansion of the half-quotient D2 / hτ2 i.

identical graphs; see Fig. 4.7. Similarly, a list may contain several half-edges; see Fig. 4.8. Because of the
second part of Lemma 4.5, the loops pose no problem. On the other hand, one half-edge may be contained
in lists of several different pendant elements which are expanded to non-isomorphic subgraphs in H; see
Fig. 4.7. This creates the main difficulty for our algorithm, leading to the bottleneck in form of a slow
subroutine requiring time O∗ (2e(H)/2 ).
Reductions with Lists. We want to compute the reduction series with lists H = R0 , R1 , . . . , Rt ending
with a primitive graph Rt with attached pendant elements with computed lists. We construct R0 by replacing
all pendant edges and loops by pendant elements with singleton lists.
Suppose that we know Ri , and we want to apply one step of the reduction and compute Ri+1 . We find
all atoms in Ri . We define atoms with respect to the chosen core in H, and we work with pendant elements
as with pendant edges. Further, we consider only star block atoms consisting only of an articulation with
all its descendants attached in form of reduced pendant elements. This means that we postpone reduction
of star block atoms till all their descendants are reduced first. (The same modification could be applied in
all reductions as well, but it is important here.)
To construct Ri+1 from Ri , we proceed with the following:
• We replace dipoles and proper atoms by edges of the corresponding colors from the catalog. A
proper atom might have pendant elements attached to its interior, but these pendant elements are
always realized by edges corresponding to the edge-quotients of some block atoms. Therefore, we
can replace the pendant elements with lists by the unique edges from these lists, and if some list
contains no edge, we stop the reduction. We run a catalog query and if the dipole or proper atom
is not contained in the catalog, we halt the reduction procedure.
• We replace block atoms by pendant elements with constructed lists. If some list is empty, we again
halt the reduction.
It remains to describe the construction of the lists for the created pendant elements.
Computing Lists. Let A be a block atom in Ri , replaced by a pendant element x in Ri+1 , and we want
to compute L(x). We compute L(x) from the lists of the pendant elements attached to A. Suppose that
A has pendant elements y1 , . . . , yp attached. For each member of L(x), we remember which members of
L(y1 ), . . . , L(yp ) have to be chosen for its expansion.
Lemma 4.6. Let A be a non-star block atom in Ri . Assuming (P3), we can compute the list L(x) of
the pendant element x corresponding to A in polynomial time.
Proof. We iterate over quotients in the catalog which are K2 with a single pendant edge, essentially
cycles, or essentially 3-connected graphs by Lemma 3.7. Let Q be such a quotient. For u ∈ ∂A, we put
L(u) = ∂Q. For each single pendant element y of A attached at u, we construct L(u) consisting of all vertices
v ∈ V (Q) such that the pendent edge/loop/half-edge attached at v belongs to L(y). We remove all pendant
elements attached at A and all pendant edges/loops/half-edges attached at Q.
By definition of pendant elements, it is possible to expand Q to the block part corresponding to A if
L
and only if there exists a list-compatible isomorphism A −→
Q. If Q is K2 or a cycle, we test it trivially. If
L
Q is 3-connected, we test it using (P3). If A −→ Q, we add the pendant edge/loop/half-edge representing
L
this quotient to the list L(x), and we remember the constructed isomorphism A −→
Q. See Fig. 4.9 for an
example.
On the other hand, if A is a star block atom, we compute its list by a slow subroutine. If this slow
subroutine can be avoided and the list for A can be computed in polynomial time, the entire meta-algorithm
of Theorem 1.3 runs in polynomial time.
Lemma 4.7. Let A be a star block atom in Ri . We can compute the list L(x) of the pendant element x

24

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

n

o

,
?

n

?
?

n

,

,

o
A1

A
o

A2

Fig. 4.9. On the left, a non-star block atom A in Ri with depicted lists of its pendant elements. On the right, two
possible atoms from the catalog having a quotient for which there exists a list-compatible isomorphism from A. So the list of
the pendant element replacing A in Ri+1 contains the pendant edge corresponding to the edge-quotient of the block atom A1
and the half-edge corresponding to a half-quotient of the proper atom A2 .

corresponding to A in time O∗ (2e(H)/2 ).
Proof. Each star block atom of Ri corresponds either to the edge-quotient of a star block atom, or
to the loop- or a half-quotient of a dipole. Lemma 3.20 states that a dipole can have exponentially many
pairwise non-isomorphic half-quotients, we iterate over all of them which gives 2e(H)/2 part in the complexity
bound. Since we postpone reduction of star block atoms, all pendant elements of A necessarily correspond
to non-star block atoms in some Rj , for j < i, so each pendant element corresponds in H to one subtree of
blocks attached at the vertex of A.
Case 1: Dipoles. We iterate over all partially expanded dipoles in the catalog and try to add them to
the list L(x). Let D be a partially expanded dipole, recall that all edges of D correspond to proper atoms.
We test whether the lists of the pendant elements attached to the star block atom A are compatible
with the loop-quotient of D. Each loop of this loop-quotient corresponds to the loop-quotient of some proper
atom which is either a cycle with attached single pendant edges, or essentially 3-connected by Lemma 3.8.
Therefore, it corresponds to exactly one pendant element in A. By Lemma 4.5, each loop belongs only to
lists of pendant elements of type. Therefore, we just need to compare the number of loops in each color class
with the number of lists containing this colored loop. If these numbers match, we add the loop representing
the loop-quotient of D to L(x).
Then we iterate over all half-quotients of D. By Lemma 3.20, let Q be one of its at most 2e(H)/2 possible
quotients. Recall from Section 3 that an edge of D projects either to a half-edge, or together with another
edge of D of the same color and type to one loop. So each Q consists of loops and half-edges attached to a
vertex. Since all edges of D correspond to proper atoms, each loop and each half-edge has to be matched to
one pendant element of A.
Therefore, we test existence of a perfect matching in the following bipartite graph: One part is formed by
the loops and the half-edges of Q, and the other part is formed by the pendant elements of A. A loop/halfedge is adjacent to a pendant element, if and only if the corresponding list contains this loop/half-edge. Each
perfect matching defines one assignment of the loops and half-edges of Q to the pendant elements of A. See

n

,

?
A

?
n

o

,

?
?
o

n

,

o

n

,

o

n

,

o

n

,

o

n

,

o

n

,

o

D

Q

Fig. 4.10. The half-edge corresponding to a half-quotient of the dipole D belongs to the list L(x) of a pendant element x
replacing A because there exists a perfect matching between the loops and half-edges of the half-quotient Q of D and the lists
of pendant elements of A.

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

25

Fig. 4.10 for an example. We add the half-edge corresponding to a half-quotient of D to L(x) if and only if
there exists a perfect matching for at least one half-quotient Q of D.
Case 2: Star Block Atoms. We iterate over all partially expanded star block atoms of the catalog, let S
be one of them. The star block atom S consists of one vertex with attached pendant edges (corresponding
to non-star block atoms), loops (corresponding to the loop-quotients of proper atoms) and half-edges. Some
of these half-edges correspond to dipoles, and some to proper atoms. Let h1 , . . . , hd be the half-edges
corresponding to partially expanded dipoles D1 , . . . , Dd from the catalog. We construct all expanded edgequotients Q of S by replacing h1 , . . . , hd by all possible choices of half-quotients Q1 , . . . , Qd of D1 , . . . , Dd .
In total, we have at most 2e(H)/2 different expanded edge-quotients Q of S.
All pendant edges of Q correspond to non-star block atoms, and all loops and half-edges correspond to
loop- and half-quotients of proper atoms. Therefore, every edge, loop and half-edge attached in Q has to
be matched to one pendant element of A. Similarly as above, for each expanded edge-quotient Q, we test
whether there exists a perfect matching between edges, loops and half-edges of Q and the lists of pendant
elements of A. We add the edge representing the edge-quotient of the star block atom S to L(x), if and only
if there exists a perfect matching for some expanded edge-quotient Q of S.
The procedure computes the list L(x) correctly since we test all possible quotients from the catalog, and
for each quotient we test all possibilities how it could be matched to A. For each quotient Q, the running
time is clearly polynomial, and we have O∗ (2e(H)/2 ) quotients.
Algorithm 2 gives the pseudocode for computation of the list L(x) of a pendant element x replacing an
atom A. If the returned list is empty, we halt the reduction; either Hs is not expandable to H, or we have
chosen a wrong core in H.
Testing Expandibility. The reduction with lists ends with a primitive graph Rt with lists. For one
particular choice of a core, Rt represents the set of graphs Ht to which H can be reduced.
L
In the following, we denote by Rt −→
Hs existence of a list-compatible isomorphism which preserves
colors and orientations of edges and maps pendant elements x of Rt into pendant edges, loops and half-edges
of Hs such that π(x) ∈ L(x). (It corresponds to a list-compatible isomorphism defined in Section 1 when
pendant elements/edges/loops/half-edges are removed, as described in the proof of Lemma 4.6.)
L
Lemma 4.8. The graph Hs is expandable to H0 which is isomorphic to H if and only if Rt −→
Hs for
some choice of the core in H.
L
Proof. Suppose that Rt −→
Hs for some choice of the core. By the definition, every pendant element x of
Rt can be replaced by any member of L(x) which can be fully expanded to the block part in H corresponding
to x. The list-compatible isomorphism chooses for pendant elements of Rt realization by edges, loops and
half-edges which is compatible with the computed quotient of Hs .
In more detail, we first expand edges in Hs , . . . , Hr+1 by the unique edge-quotients to reach Hr , this
L
has to be compatible with the sequence of replacements defined by Rt −→
Hs . Then we do replacements in
the manner of Theorem 3.18, and construct the expansions Hr−1 , . . . , H0 . Since we expand according to the
L
list-compatible isomorphism Rt −→
Hs , the constructed graph H0 is isomorphic to H.
On the other hand, suppose that Hs is expandable to H0 which is isomorphic to H. Then according to
Lemma 3.21, the core of Hs is preserved in H, so it has to correspond to some block or to some articulation
of H, which we choose as the core of H. Since there exists a sequence of replacements from Hs which
L
constructs H0 , this sequence of replacements is possible in Rt . Thus Rt −→
Hs .
Lemma 4.9. Assuming (P3), we can test whether Hs is expandable to H0 which is isomorphic to H in
time O∗ (2e(H)/2 ).
Proof. We iterate over all choices of the core in H. For each, we compute the reduction series with lists
H = R0 , . . . , Rt , using Algorithm 2 and Lemmas 4.6 and 4.7. We modify both graphs Rt and Hs similarly
as in the proof of Lemma 4.6. For each pendant element x of Rt attached at u, we put L(u) be the set of all
vertices of V (Hs ) having an attached pendant edge/loop/half-edge which belongs to L(x), and we remove
x. We remove all pendant edges/loops/half-edges of Hs .
L
Then we test whether Rt −→
Hs . It is trivial to deal with the cases when Hs or Rt are cycles, K2 or
L
K1 . Otherwise by Lemma 3.5, both Hs and Rt are 3-connected graphs, and we test Rt −→
Hs using (P3).
By Lemma 4.8, this subroutine is correct and runs in time O∗ (2e(H)/2 ).
4.4. Proof of The Main Theorem. Now, we are ready to establish the main algorithmic result of
the paper; see Algorithm 3 for the pseudocode. Assuming that a class C satisfies (P1) to (P3), we show that
RegularCover can be solved for C-inputs G in time O∗ (2e(H)/2 ):

26

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Algorithm 2 The subroutine for computing lists of pendant elements
Require: A block atom A of Ri .
Ensure: The list L(x) of the pendant element x replacing A in Ri+1 .
1:
2:
3:
4:
5:
6:
7:

8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

21:

Initiate the empty list L(x).
if A is a non-star block atom then
Iterate over all quotients from the catalog.
for each quotient Q from the catalog do
For each pendant element x of A attached at u, set L(u) to all vertices V (Q) having an attached
pendant edge/loop/half-edges belonging to L(x), and remove x.
L
Remove all pendant edges/loops/half-edges in Q, and test A −→
Q (trivially or using (P3)).
If some list-compatible isomorphism exists, we add the edge/loop/half-edge of Q to L(x) together
with this list-compatible isomorphism.
if A is a star block atom then
Iterate over all partially expanded dipoles D and star block atoms S in the catalog.
for each partially expanded dipole D do
Test whether the loop-quotient of D matches the lists; if yes, then add the loop representing D to
L(x).
Iterate over all half-quotients Q of D.
for each half-quotient Q do
Test existence of a perfect matching between the loops and half-edges of Q and the lists of the
pendant elements of A.
If a perfect matching exists, add the half-edge of D to L(x) together with this half-quotient Q
and this matching, and proceed with the next dipole.
for each partially expanded star block atom S do
Compute all expanded edge-quotients Q of S by replacing the half-edges h1 , . . . , hd corresponding
to the dipoles by all possible combinations of their half-quotients Q1 , . . . , Qd .
for each expanded edge-quotient Q do
Test existence of a perfect matching between the edges, loops and half-edges of Q and the lists of
the pendant elements of A.
If a perfect matching exists, then add the edge of S to L(x) with this expanded edge-quotient Q
and this matching, and proceed with the next star block atom.
return The constructed list L(x).

Proof. [Theorem 1.3] We recall the main steps of the algorithm and discuss their time complexity. The
reduction series G0 , . . . , Gr can be computed in polynomial time, by Lemmas 3.15 and 4.4. We reach in
Gr one of primitive graphs characterized in Lemma 3.5. If Gr is essentially 3-connected, the property (P2)
ensures that there are polynomially many semiregular subgroups Γr of Aut(Gr ) which can be computed in
polynomial time. If Gr is K2 with attached single pendant edges or essentially a cycle, it is true as well.
For each of these subgroups Γr , we compute the quotient Hr = Gr /Γr . Then we compute the reduction
series Hr , . . . , Hs , again in polynomial time using Lemma 4.4. Using Lemma 4.9, we test in time O∗ (2e(H)/2 )
whether Hs is expandable to H0 which is isomorphic to H. We output “yes” if and only if Hr = Gr /Γr is
expandable to H0 isomorphic to H for at least one the subgroups Γr .
To certify the “yes” outputs, we construct the semiregular subgroup Γ ≤ Aut(G) such that G/Γ ∼
= H as
L
follows. If Rt −→
Hs for some choice of the core in H, this list-compatible isomorphism describes how to
expand Hs to H0 which is isomorphic to H using Theorem 3.18. This expansion replaces edges, loops and
half-edges with edge-quotients, loop-quotients and some choices of half-quotients. The expansion towards
Hr is deterministic since no half-edges are replaced.
We expand Hr , . . . , H0 , together with constructing group extensions Γr−1 , . . . , Γ0 of Γr , where Γi is a
semiregular subgroup of Aut(Gi ). When Gi+1 is expanded to Gi , we replace some edges with interiors of
some atoms. In the common parts, we define the actions of Γi and Γi+1 the same. It remains to define the
action of Γi on the interiors of these atoms in such a way that Gi /Γi = Hi . When some orbit of atoms
is projected to the edge- or loop-quotients, then we isomorphically swap their interiors in Γi the same as

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

27

Algorithm 3 The meta-algorithm for regular covers – RegularCover
Require: A graph G of C satisfying (P1), (P2) and (P3), and a graph H.
Ensure: A semiregular subgroup Γ ≤ Aut(G) such that G/Γ ∼
= H if it exists.
1:
2:

3:
4:
5:
6:
7:
8:

9:
10:
11:
12:
13:
14:
15:
16:
17:

18:
19:
20:
21:

22:
23:
24:

Compute the reduction series G0 , . . . , Gr ending with the primitive graph Gr .
During the reductions, we use Algorithm 1 to add atoms and their quotients into the catalog, and to
replace them with colored edges.
Using (P2), we compute all semiregular subgroups Γr of Aut(Gr ).
for each semiregular subgroup Γr do
Compute the quotient Hr = Gr /Γr .
Choose, say, the central block/articulation of Hr as the core.
Compute the reduction series Hr , . . . , Hs with respect to the core.
During the reductions, we use Algorithm 1 to add atoms into the catalog, and to replace them with
colored edges.
for each guessed position of the core in H do
Compute the reduction series with lists H = R0 , . . . , Rt .
to compute Ri+1 from Ri do
for each proper atom or dipole A in Ri do
if A is a proper atom then
Replace its pendant elements with the unique pendant edges from their lists. If some list
contains no pendant edge, halt and test for other choices of the core in H.
Replace A with a colored edge using the catalog. Halt and test for other choices of the core in
H if A is not in the catalog.
for each block atom A in Ri do
Replace it by a pendant element x whose list L(x) is computed using Algorithm 2. Halt and
test for other choices of the core in H if L(x) is empty.
L
Test Rt −→
Hs using Lemma 4.9.
L
if Rt −→ Hs then
Using the lists, compute the expansions Hs−1 , . . . , H0 such that H0 ∼
= H.
Using Theorem 3.18, compute the group extensions Γr−1 , . . . , Γ0 = Γ to the interiors of expanded edges, loops and half-edges. For half-edges, use involutions τ on interiors of replacing
half-quotients.
By Lemma 4.8, G/Γ ∼
= H, so the group Γ defines the regular covering projection p : G → H.

return The semiregular subgroup Γ ≤ Aut(G).
return The graph G does not regularly cover the graph H.

the corresponding edges are swapped in Γi+1 . For an orbit which is projected to half-quotients, we further
compose some automorphisms of Γi with the half-quotient defining semiregular involution τ on their interior
(when the corresponding edges are flipped in Γi ). For more details, see [26], proofs of Lemma 4.7 and
Theorem 1.3 therein.
It remains to argue correctness of the algorithm. First suppose that the algorithm succeeds. We construct
a semiregular subgroup Γ of Aut(G). By Lemma 4.8, some Hs is expandible to H0 which is isomorphic to
H. By Theorem 3.18, we get that G/Γ ∼
= H which proves that G regularly covers H. On the other hand,
suppose that there exists a semiregular Γ such that H ∼
= G/Γ. Then Γ corresponds to the unique semiregular
subgroup Γr on Gr which is one of the semiregular subgroups tested by the algorithm. Therefore Hr has to
be expandable to H0 isomorphic to H, and we detect this correctly according to Lemma 4.8.
Next, we prove two corollaries. The first corollary states that if G is 3-connected, H is 2-connected or
k = |G|/|H| is odd, the meta-algorithm can avoid the slow subroutine of Lemma 4.7 and can be modified to
run in polynomial time.
Proof. [Corollary 1.4] If G is 3-connected, then it is primitive, so G = Gr . Therefore, we compute all
quotients Hr = Gr /Γr , and test using Lemma 3.16 whether Hr ∼
= H. No reduction with lists needs to be
applied. If H is 2-connected, no pendant elements are created the reduction of H with lists, so the slow

28

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

n 3× o n2×o
,
A

?

?

?
?
?

Ri

?

?

?

n 3× o
,
5×

n 2× o
,

2×
D1

n3×o

3×

S
red.

n 4× o
,
n 3× o n 3× o
,
,

Fig. 5.1. On the left, a star block atom A in Ri with 23 attached pendant elements, together with their lists and
multiplicities. On the right, a star block atom S from the catalog which belongs to L(x). The bold dashed edges correspond to
the partially expanded dipole D1 whose edges are depicted with multiplicities, the remaining colored edges correspond to proper
atoms.

subroutine can be avoided and even the assumptions (P1), (P2) and (P3∗ ) are sufficient.
If |Γ| = |Γr | is odd, then no half-edges occur in Hr , and so according to Corollary 3.19, the expansion
gives the unique graph H0 . We just test whether H0 ∼
= H.
Next, we prove that we can modify the meta-algorithm to output all regular quotients of G, with a
polynomial-time delay.
Proof. [Corollary 1.5] We compute the reduction series G = G0 , . . . , Gr and all semiregular subgroups
Γr of Aut(Gr ). Next, we run all possible expansions of Hr = Gr /Γr to H0 using Theorem 3.18, by all
possible choices of half-quotients. All half-quotients of proper atoms can be computed in polynomial time.
For dipoles, we can easily generate them with polynomial-time delays. We output all constructed graphs
H0 .
5. Star Blocks Atoms with Lists. The bottleneck in the running time of the meta-algorithm of
Theorem 1.3 is the single slow subroutine in Lemma 4.7, computing lists of pendant elements replacing star
block atoms in Ri . In this section, we give insights into this problem, which might lead to a faster algorithm
for RegularCover of planar graphs.
We show a combinatorial reformulation to finding a certain generalization of a perfect matching which
we call IV-Matching. Here we describe a complete derivation of this problem, and in Conclusions we just
give its combinatorial statement.
Instance. Figure 5.1 shows an example. Suppose that Ri contains a star block atom A with attached
pendant elements, each with a previously computed list and corresponding to a non-star block atom. We
want to determine the list L(x) of the pendant element x replacing A in Ri+1 . The following are the
candidates for members of L(x):

unified dipoles
S

4×
S

8×
D

Fig. 5.2. We apply the unification on the example in Fig. 5.1 as follows. We unify both occurances of the dipole D1 into
the dipole D. Since the colored classes of gray edges have odd sizes, we attach one half-edge per dipole from each class directly
to S.

29

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

• Each loop corresponding to the loop-quotient of a dipole D.
• Each half-edge corresponding to a half-quotient of a dipole D.
• Each edge corresponding to the edge-quotient of a star block atom S.
Since loop-quotients of dipoles are uniquely determined, we can easily test them and we can ignore
them. The case of a half-quotient of a dipole D can be reduced to a star block atom S with a single half-edge
attached corresponding to a half-quotient of D. If S can be matched to A, we instead add the half-edge
corresponding to a half-quotient of D to L(x). Therefore, in the remainder of this section, we only deal with
the case of a star block atoms S. We want to decide whether the edge corresponding to the edge-quotient
of S belongs to L(x). We shall assume that at least one half-edge attached in S corresponds to a dipole,
otherwise the problem is trivial.
Outline. In Section 5.1, we simplify both A and S. In Section 5.2, we further apply size constraints to
simplify them. In Section 5.3, we derive the IV-Matching problem.
5.1. Preprocessing Star Block Atoms. The star block atom S has several pendant edges, loops and
half-edges attached. Further, we may assume that S is partially expanded (see Section 4.2), so its pendant
edges correspond to non-star block atoms and its loops correspond to proper atoms. On the other hand, a
half-edge can be of two types: either it corresponds to a half-quotient of a proper atom, or of a dipole. For
example, in Fig. 5.1 we have two half-edges corresponding to proper atoms, and two half-edges corresponding
to dipoles. Further, we may assume that all these dipoles are partially expanded (see Section 4.2), so all
their edges correspond to proper atoms.
Unifying Dipoles. Recall that every half-quotient of a dipole consists of half-edges and loops attached to
one vertex. Since S may contain multiple half-edges corresponding to half-quotients of dipoles, we want to
unify them into one dipole D containing all their edges. (This may happen in the quotients; see Fig. 5.3.)
The issue is that this unification might introduce additional quotients of D as in Fig. 5.3. If two dipoles
both contain an odd number of edges of one color, the unified dipole D has a half-quotient consisting of
only loops of this color which is not possible in the case of half-quotients of two separated dipoles. There is
an easy fix: we check each dipole and we remove one edge from each color class of odd size (of necessarily
halvable edges) and attach the half-edge of this color directly to S. At least one half-edge of this color
appears in every half-quotient of this dipole, so the possible half-quotients are not changed. In Fig. 5.2, we
illustrate this preprocessing for the example in Fig. 5.1.
Non-halvable Edges of The Dipole. If the dipole D contains some non-halvable edges, then they are
paired in every half-quotient of D and form loops. We remove them from D and attach the corresponding
number of loops directly in S. After this step, the dipole D contains only even number of halvable edges in
each color class.

ex

p.

Attached Pendant Edges and Loops. The star block atom S may have some pendant edges (corresponding to non-star block atoms) and loops (corresponding to proper atoms) attached. Therefore, each attached
pendant edge/loop corresponds to exactly one pendant element of A. By Lemma 4.5, each is contained in
list of only one type of pendant elements, all corresponding to isomorphic block parts in H. Therefore, we
can arbitrarily assign pendant elements, remove them from A and remove these pendant edges and loops
from S.

exp.

Γr

red.

ex

Gr

Hr

p.

Gr−1

Hr−1

Fig. 5.3. For Γr generated by two reflections, the quotient Hr consists of a star block atom with two half-edges corresponding to dipoles. All three expansions Hr−1 up to isomorphism are depicted. But it is not possible to expand Hr to the
quotient with three attached loops.

30

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

Summary. By the preprocessing of S and A described above, we may assume the following. The star block
atom S has only half-edges attached, all but one corresponding to proper atoms. The remaining half-edge
corresponds to the unified dipole D having only color classes of even sizes of halvable edges corresponding
to proper atoms.
For each pendant element x of A, the list L(x) contains only half-edges (attached in S or in a half-quotient
of D) and loops (corresponding to halvable edges of D).
5.2. Sizes and Chains. To simplify the problem further, we study sizes of atoms and their quotients.
Let A be an atom and let Q be a quotient of this atom. Depending on the type of Q, we get:
• Q is the edge-quotient: Then v(Q) = v(A) and e(Q) = e(A).
• Q is the loop-quotient: Then v(Q) = v(A) − 1 and e(Q) = e(A).
• Q is a half-quotient: Then v(Q) = v(A)/2 and e(Q) = e(A)/2.
Sizes of Expanded Subgraphs and Quotients. Throughout each reduction, we calculate how many
vertices and edges are in all the atoms replaced by colored edges which we denote by v̂ and ê. Initially, we
put v̂(e) = 0 and ê(e) = 1 for every edge e ∈ E(G0 ). For a subgraph X, we define
X
X
ê(e).
v̂(e),
and
ê(X) :=
v̂(X) := v(X) +
e∈E(X)

e∈E(X)

When an atom A is replaced by an edge e in the reduction, we put v̂(e) = v̂(Å) and ê(e) = ê(Å). For
a subgraph X of Gi , the numbers v̂(X) and ê(X) are the numbers of vertices and edges when X is fully
expanded.
We similarly define v̂ and ê for quotients and their subgraphs; the difference is that the quotients may
contain half-edges. For a half-edge h ∈ H(X), created by halving an edge e, we put v̂(h) = v̂(e)/2 and
ê(h) = ê(e)/2. For a subgraph X, we define
X
X
X
X
ê(h).
ê(e) +
v̂(h),
and
ê(X) :=
v̂(e) +
v̂(X) := v(X) +
e∈E(X)

h∈H(X)

e∈E(X)

h∈H(X)

Sizes of Pendant Elements. We also inductively define v̂ and ê for pendant elements x and subgraphs
X of R0 , . . . , Rt . Initially, we put v̂(e) = 0 and ê(e) = 1 for every edge e ∈ E(R0 ). For a subgraph X of
Ri , let P (X) be the set of all pendant elements in X. We define
X
X
X
X
ê(y),
ê(e) +
v̂(ẙ),
and
ê(X) :=
v̂(e) +
v̂(X) := v(X) +
e∈E(X)

y∈P (X)

e∈E(X)

y∈P (X)

while for a pendant element x corresponding to an atom A in Ri , we define v̂(x) = v̂(A), v̂(x̊) = v̂(Å) =
v̂(x) − 1, and ê(x) = ê(A).
Restricting Lists by Sizes. Next, we show that these sizes can restrict possible members of lists of pendant
elements:
Lemma 5.1. For a pendant element x, the possible pendant edge and all loops and half-edges of the list
L(x) have the same v̂ and ê as v̂(x) and ê(x), respectively.
Proof. The pendant element x corresponds to a block part of H. All members of L(x) can be fully
expanded to graphs isomorphic to this block part. Necessarily, these graphs contain the same number of
vertices and edges as v̂(x) and ê(x).
When L(x) is computed, we can only consider quotients of the correct sizes, speeding up Algorithm 2.
For pendant edges and loops, each belongs to lists of only one type of pendant elements by Lemma 4.5. This
is not true for half-edges and for purpose of this section, the following is important:
Corollary 5.2. Let x and y be two pendant elements.
(i) If L(x) and L(y) share a half-edge, then v̂(x) = v̂(y) and ê(x) = ê(y).
(ii) Let L(x) contain a loop of a color c and a half-edge of a color c′ . Then L(y) cannot contain both the
loop of the color c′ and the half-edge of the color c.
Proof. (i) Implied by Lemma 5.1.
(ii) Let L(x) contain a loop e and L(y) contain a half-edge h of the same color. Then v̂(x) = v̂(e)+ 1 and
v̂(y) = v̂(e)/2 + 1 for the vertices, and ê(x) = ê(e) and ê(y) = ê(e)/2 for the edges. Therefore x corresponds

31

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

level 0
n

o

,
n

level 1

o

v̂ ≡ α
ê ≡ β

level 2

n

,

o

n

,

o

n

o

v̂ ≡ 2α − 1
ê ≡ 2β

n
n

level 3

,

o

,

o

v̂ ≡ 4α − 3
ê ≡ 4β

n

,

o

v̂ ≡ 8α − 7
ê ≡ 8β

Fig. 5.4. A chain of pendant elements with four levels, which is the only chain in Fig. 5.1, for some α and β (we ignore
multiplicities of pendant elements). Notice that quotients corresponding to one atom are placed in neighboring levels.

to a larger block part in H than y. By the same argument, we deduce that y corresponds to a larger block
part in H than x, which gives a contradiction.
The property (i) relates half-edges together. The property (ii) states that there is a certain size hierarchy
on the pendant elements discussed below.
Chains of Pendant Elements. Pendant elements can be partitioned into independent chains, each further
partitioned into several levels. The level of size (α, β) consists of all pendant elements x having v̂(x) = α
and ê(x) = β. Each chain starts with the level 0 of some size (α, β). Further, it contains the levels m > 0
of sizes (2m α − (2m − 1), 2m β). See Fig. 5.4 for an example.
The key property is the following: if L(x) contains a half-edge of a color c and L(y) contains the loop
of the same color c, then x belongs to a level m and y belongs to the level m + 1 of the same chain. A star
block atom A can contain multiple chains, but different chains contain completely different colors in their
lists, so they are completely independent.
Summary. We may partition S, D, and A according chains of pendant elements of A and test them
separately. Therefore, we may assume that there is exactly one chain of pendant elements in A, and only
the corresponding edges in D and half-edges in S.
5.3. Reduction to the IV-Matching Problem. The star block atom S contains a half-edge corresponding to the dipole D and let H ′ (S) be the set of the remaining half-edges corresponding to proper
atoms. The dipole D has the following half-quotients Q. For each color class of an even size s, we choose an
arbitrary integer ℓ such that 0 ≤ ℓ ≤ 2s , and attach ℓ loops and s − 2ℓ half-edges of this color in Q.
If these values s and ℓ are known for each color class, we can test existence of a perfect matching as
described in the proof of Lemma 4.7. Since they are not known, we need to solve a generalization of perfect
matching called IV-Matching which includes choosing of these values as a part of the problem.
Definition of the Problem. The input of IV-Matching gives the following bipartite graph B. We have
V (B) = P (A) ∪ E(D) ∪ H ′ (S). For e ∈ E(D) of a color c and x ∈ P (A), we have ex ∈ E(B) if and only
if the half-edge or the loop of the color c belongs to the list L(x). We call the former case a half-incidence
and the latter case a loop-incidence. Further, we have a half-incidence hx ∈ E(B) between h ∈ H ′ (S) of a
color c and x ∈ P (A) if and only if the half-edge of the color c belongs to L(x).
We ask whether there exists a spanning subgraph B ′ of B, called an IV-subgraph of B, satisfying the
following properties. Each component of connectivity of B ′ is a path of length one or two (corresponding to
I and V in the name). Each x ∈ P (A) is in B ′ either half-incident to exactly one vertex in E(D) ∪ H ′ (S),
or it is loop-incident to exactly two edges e, e′ ∈ E(D) of the same color class. Further, each vertex of
E(D) ∪ H ′ (S) is incident in B ′ to exactly one x ∈ P (A). See Fig. 5.5 for an example, with several additional
properties which we discuss below.
Level Structure. The structure of levels of the chain of pendant elements transfers into the level structure
of B. The part P (A) is partioned into levels called A levels. Every half-edge h ∈ H ′ (S) is half-incident only
to vertices of the A level m of the size (v̂(h), ê(h)). Every edge e ∈ E(D) is half-incident only to vertices
of the A level m of size (v̂(e)/2, ê(e)/2) and loop-incident only to vertices of the A level m + 1 of the size
(v̂(e) − 1, ê(e)). Therefore, we can define S levels for the part E(D) ∪ H ′ (S) such that an S level m contains

32

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

A level 0

S level 0

A level 1

S level 1

A level 2

S level 2

4×
n 3× o
,
n2×o

halfincidences

4×
n 3× o
,

4×

1×

A level 3

8×

n 2× o
,

2×

n3×o
loopincidences

halfincidences

n 4× o
,

4×

n 3× o
,

3×

loopincidences

halfincidences

n 3× o
,

loopincidences

Fig. 5.5. The instance of the IV-Matching problem corresponding to the input A in Fig. 5.1 and the preprocessed star
block atom S in Fig. 5.2. The edges E(B) are depicted in gray and an IV-subgraph B ′ is highlighted in bold. We have I’s
between half-incidences and V’s between loop-incidences. The part P (A) is in elipses, the other part E(D) ∪ H ′ (S) is in boxes.
The lists P (A), the edges E(D) and the half-edges H ′ (S) are depicted together with multiplicities.

all vertices half-incident to the A level m or loop-incident to the A level m + 1. If we depict all levels from
left to right according to their order, alternating A levels and S levels, all edges of B go between consecutive
levels as depicted in Fig. 5.5.
Clusters. We can view B as a cluster graph. In each S level, E(D) and H ′ (S) form clusters according
to their color classes, called edge clusters and half-edge clusters respectively. In each A level, the pendant
elements form pendant element clusters according to equivalence classes of their lists. (We note that two
pendant elements with equal lists can correspond to non-isomorphic subgraphs in H. Then their lists contain
only half-edges.) Two clusters are either completely adjacent, or not adjacent at all: the subgraph induced
by the union of two clusters is either a complete bipartite graph, or contains no edges.
Each pendant element cluster may be loop-adjacent to several edge clusters. On the other hand, each
edge cluster is loop-adjacent to at most one pendant element cluster: the loop of the corresponding color
belongs to at most one isomorphism class of pendant elements by Lemma 4.5. There are no constraints for
half-incidences between clusters.
Only Logarithmically Many Levels. The sizes of graphs are growing exponentially with the level number.
Therefore, we have at most logarithmically many levels with respect to the size of the input graph H.
Complexity. Since IV-Matching can be used to solve the slow subroutine of Lemma 4.7, we get the
following in relation to the meta-algorithm of Theorem 1.3:
Proposition 5.3. If the IV-Matching problem can be solved for logarithmically many levels in polynomial time, then we can modify the meta-algorithm of Theorem 1.3 to run in polynomial time as well.
Unfortunately, Folwarczný and Knop [28] recently proved that this problem is NP-complete, even for two
A levels. Nevertheless, we believe that the particular instances arizing from the RegularCover problem
might be solvable in polynomial time and the properties described in this section might be useful for that.
Numbers of Edges Between Levels. We do not know how many half- and loop-incidences are in B ′ at
each cluster, otherwise we could solve the problem directly by finding a perfect matching in a modified graph.
On the other hand, these numbers are determined between consecutive A levels and S levels as follows. Let
am be the number of pendant elements in the A level m and let sm be the number of edges and half-edges
in the S level m. Let B ′ be an IV-subgraph and let bi and b′i be the numbers of edges in B ′ between the A
level i and the S level i, and between the S level i and the A level i + 1, respectively.
Every pendant element in the A level 0 is half-incident in B ′ to the S level 0, so b0 = a0 . Therefore,
the number of remaining vertices in the S level 0 is s0 − b0 . These vertices are loop-incident in B ′ to the A
b′
level 1, so b′0 = s0 − b0 and a1 − 20 pendant elements remain in the A level 1. We can proceed in this way
further, and we get the following inductive formulas:
b i = ai −

b′i−1
,
2

and

b′i = si − bi .

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

S4

C2 × S 4

33

C2 × A5

Fig. 6.1. The five platonic solids together with their automorphism groups.

Clearly, each number b′i has to be even, otherwise no IV-subgraph exists.
6. Applying the Meta-algorithm to Planar Graphs. In this section, we discuss automorphism
groups of 3-connected planar graphs and we show that the meta-algorithm of Theorem 1.3 applies to the
class of planar graphs.
Automorphism Groups. A group is spherical if it is the group of the symmetries of a tiling of the sphere.
The first class of spherical groups are the subgroups of the automorphism groups of the platonic solids, i.e.,
S4 for the tetrahedron, C2 × S4 for the cube and the octahedron, and C2 × A5 for the dodecahedron and
the icosahedron; see Fig. 6.1. The second class of spherical groups is formed by the infinite families Cn , Dn ,
Cn × C2 , and Dn × C2 .
A map M is a 2-cell embedding of a graph G onto the sphere. A rotation at a vertex is a cyclic ordering
of the edges incident with the vertex. An angle is a triple (v, e, e′ ) where v is a vertex, and e and e′ are two
incident edges which are consecutive in the rotation at v or in the inverse rotation at v. An automorphism
of a map is an automorphism of the graph which preserves the angles; in other words the rotations are
preserved. For a 3-connected planar graph G, we have Aut(G) ∼
= Aut(M) and it is a spherical group. For
more details, see [26] and the references therein.
Lemma 6.1. For a 3-connected planar graph G, we can compute Aut(G) in time O(v 2 (G)).
Proof. Compute the unique map M of G. There are O(v(G)) angles in M. We fix one angle (v, e, e′ ),
and test for each other angle whether there is an automorphism mapping (v, e, e′ ) to it. The key observation
is that this partial mapping has a unique extension to a mapping compatible with the rotations of M. We
can just test in O(v(G)) whether it is an automorphism. The total running time is O(v 2 (G)).
Properties (P1) to (P3). We are ready to establish the following:
Lemma 6.2. The class of planar graphs satisfies (P1) to (P3).
Proof. The class of planar graphs clearly satisfies (P1). For (P2), Lemma 6.1 allows to compute Aut(G)
in time O(v 2 (G)). Since it is a spherical group, we can generate all linearly many subgroups and check which
ones act semiregularly. The property (P3) holds for projectively planar graphs since ListIso can be solved
in time O(v 5/2 (G)) for graphs of bounded genus [41] (even for lists on both vertices and half-edges).
Proof. [Theorem 1.1] By Lemma 6.2, we can apply Theorem 1.3.
Half-quotients of Planar Proper Atoms. Let A be a planar proper atom. We know that Aut(A) is a
spherical group, and further each semiregular involution τ defining a half-quotient of A has to exchange the
vertices of the boundary. We get two types of geometrically defined quotients, depicted in Fig. 6.2.
Lemma 6.3 ([26], Lemma 5.6). Let A be a planar proper atom and let ∂A = {u, v}. There are at most
two half-quotients A/ hτ i where τ ∈ Aut(A) is an involutory semiregular automorphism transposing u and v:
(a) The rotational half-quotient – The involution τ is orientation preserving and A/ hτ i is planar with
at most one half-edge.
(b) The reflectional half-quotient – The involution τ is a reflection and A/ hτ i is planar with at least
two half-edges.
7. Concluding Remarks. This paper is based on the structural results of [26], describing behaviour
of regular graph covering with respect to 1-cuts and 2-cuts in G. In Theorem 1.3, we derive an FPT metaalgorithm for testing regular graph covers for C-inputs G where C is a class of graphs satisfying (P1) to (P3).
In particular, this meta-algorithm is tailored for the class of planar graphs (Theorem 1.1).
When working with 3-connected decomposition, we described two subroutines we need to solve. First,
we have rediscovered graph isomorphism restricted by lists, introduced by Lubiw [47], which lead to several

34

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

180◦

A+

u

A+

v

u

v

τ
τ
p

A+ / hτ i p(u)

p

A+ / hτ i p(u)

Fig. 6.2. The rotational quotient and reflectional quotient of a planar proper atom A with the added edge uv.

fruitful results in [41]. Second, we introduce a generalization of bipartite matching called the IV-Matching
problem, proved to be NP-complete by Folwarcný and Knop [28].
We conclude by several remarks and open problems.
Running Time of The Meta-algorithm. We have omitted polynomial factors in the complexity since the
main goal was to establish that RegularCover can be solved in FTP time for C-inputs G for C satisfying
(P1) to (P3). The degree of the polynomial depends on the complexity of polynomial time algorithms in
(P2) and (P3).
We roughly estimate the degree of the polynomial for running time of the algorithm of Theorem 1.1 for
planar graphs. Let n = v(G) ≥ v(H). For planar graphs, each primitive graph has O(n) quotients and each
proper atom has at most two half-quotients. Therefore, the catalog contains O(n2 ) atoms and quotients.
Each catalog query can be answered in time O(n4 ), and with a suitable canonization even in time O(n3 ).
The reduction series can be computed in time O(n) by Hopcroft and Tarjan [37], the symmetry type
of each atom can be determined in time O(n2 ) by Lemma 6.1. When adding a proper atom to the catalog,
we compute its at most two half-quotients in time O(n2 ) and compute their reduction series in time O(n4 ).
Together with catalog queries, we can compute the reduction series and Gr in time O(n5 ).
Next, we iterate over O(n) quotients Hr of Gr . For each, we compute the reduction series in time
O(n4 ). Next, we iterate over O(n) choices of the core in H. We compute the reduction series with lists
where O(n) subroutines are called. The subroutine of Lemma 4.6 runs in time O(n9/2 ) since ListIso takes
time O(n5/2 ) [41] and we compare each non-star block atom A with O(n2 ) candidates from the catalog. The
subroutine of Lemma 4.7 runs in time O(n2 2e(H)/2 ). The final test in Lemma 4.9 runs in time O(n5/2 ).
In total, the running time of the algorithm in Theorem 1.1 is O(n5 · (n5/2 + 2e(H)/2 )). By a more careful
analysis of the subroutines and possibly reordering them, it should be possible to decrease the degree little
bit.
We did not try to optimize the factor 2e(H)/2 . This estimate is certainly very rough and maybe some
further techniques from parameterized complexity can be applied to solve IV-Matching faster. We believe
that this approach should be followed only when we can prove that RegularCover is NP-complete for
planar inputs G. Also, to prove Theorem 1.3, it might be possible to design a simpler FPT algorithm running
in time O∗ (2e(H)/2 ). Our goal was to obtain as much understanding of the problem as possible, in order
to construct a polynomial time algorithm. We failed with the subroutine of Lemma 4.7, but nevertheless

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

35

further structural results may be established and the problem may be solvable in polynomial time.
Possible Extensions of The Meta-algorithm. There are several possible natural extensions of the
meta-algorithm. First, we can easily generalize it for input graph G and H with half-edges, directed edges
and halvable edges, and also for colored graphs. Further, for a regular covering testing, one can prescribe a
list L(u) ⊆ V (H) of allowed images of a regular covering projection p for each vertex u ∈ V (G) such that
p(u) ∈ L(u): the expandability testing subroutine can compute with these lists as well.
Complexity of Regular Graph Covering. By Lemmas 2.1 and 2.3, it follows that RegularCover is
GI-hard and belongs to NP. Its complexity remains an open problem:
Problem 7.1. What is the complexity of the RegularCover problem?
One possibility to attack this problem would be to prove that it is NP-hard, or to construct an efficient
algorithm using an oracle for GraphIso. If RegularCover is not NP-hard, another possibility is to prove
that RegularCover satisfies some properties which unlikely hold for any NP-hard problem. For instance
for the graph isomorphism problem, there are currently three evidences that it is unlikely NP-complete:
equivalence of existence and counting [6, 49], GraphIso belongs to coAM, so polynomial-hierarchy would
collapse if GraphIso is NP-complete [29, 55], and GraphIso can be solved in subexponential time [8].
As a possible next direction of research, we suggest to attack classes of graphs close to planar graphs,
for instance projective planar graphs or toroidal graphs. To do so, it seems that new techniques need to
be built. Even the automorphism groups of projective planar graphs and toroidal graphs are not yet well
understood.
It is natural to ask whether FPT running time of the meta-algorithm of Theorem 1.3 is needed:
Problem 7.2. Can the RegularCover problem be solved in polynomial time for C-inputs G where C
satisfies (P1) to (P3)? Can it be solved in polynomial time for planar inputs G?
The IV-Matching Problem. In Section 5, we have shown that the bottleneck of the algorithm of Theorem 1.3 reduces to a generalized matching problem called IV-Matching. Here, we describe a purely
combinatorial formulation of the IV-Matching problem. This reformulation can be useful to understand
the problem without regular covering and the structural results obtained in [26] and this paper.
The input of IV-Matching consists of a bipartite graph B with a partitioning V1 , . . . , Vℓ of its vertices
V (B) which we call levels, with all edges between of consecutive levels Vi and Vi+1 , for i = 1, . . . , ℓ − 1. The
levels V1 , V3 , . . . are called odd and the levels V2 , V4 , . . . even. Further each level Vi is partitioned into several
clusters, each consisting of a few vertices with identical neighborhoods. There are three key properties:
• The incidences in B respect the clusters; between any two clusters the graph B induces either a
complete bipartite graph, or an edge-less graph.
• Each cluster of an even level V2t is incident with at most one cluster at V2t+1 .
• The incidences between the clusters of V2t−1 and V2t can be arbitrary.
The problem IV-Matching asks whether there is a spanning subgraph B ′ called an IV-subgraph of B.
Each component of connectivity of B ′ equals to a path of length one or two. Each vertex of an odd level
V2t+1 is in B ′ adjacent either to exactly one vertex of V2t+2 , or to exactly two vertices of V2t . Each vertex
of an even level V2t is adjacent to exactly one vertex of the levels V2t−1 ∪ V2t+1 . In other words, from V2t−1
to V2t the edges of B ′ form a matching, not necessarily perfect. From V2t to V2t+1 , the edges of B ′ form
independent V-shapes, with their centers in the level V2t+1 . Figure 7.1 shows an example.
In the conference version of this paper [25], we asked as an open problem what is the complexity of the
IV-Matching problem. Recently, Folwarcný and Knop [28] answered this by proving that IV-Matching
is strongly NP-hard even for ℓ = 3. We note that this does not imply NP-hardness of RegularCover,
and it is possible that specific instances of IV-Matching arising from RegularCover can be solved in
polynomial time.
A Weaker Assumption (P2’). To make Theorem 1.3 a more natural generalization of Babai’s algorithm [5]
for graph isomorphism, it would be nice to replace (P2) with a weaker assumption:
(P2’) For a 3-connected graph G ∈ C with colored vertices and colored possibly directed edges and a
graph H with colored vertices and colored possibly directed edges, half-edges and loops, we can test
RegularCover(G, H) in polynomial time.

36

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

V1

V2

V3

4×

3×

3×

V4

4×
2×

1×

V7

4×

2×

2×

V6
4×

8×
4×

V5

3×

3×

3×
3×

Fig. 7.1. An example input B, the clusters are depicted by circles together with their sizes. The odd levels are drawn
in circles and the even ones in rectangles. The edges of B are depicted by gray lines between clusters representing complete
bipartite graphs. One spanning subgraph B ′ solving the IV-Matching problem is depicted in bold.

It is an open problem whether our meta-algorithm can be modified for C satisfying (P1), (P2’) and (P3):3
Problem 7.3. Can the RegularCover problem be solved in FPT time (with respect to the parameter
e(H)) for C-inputs G where C satisfies (P1), (P2’), and (P3)?
The modified algorithm would have to process both G and H simultaneously. For instance, it is not
needed to decide whether a proper atom is halvable or symmetric. Also, we do not need to compute all
half-quotients of a proper atom, we only need to test whether some subgraphs located in H are one of them.
There are several issues with this approach which make this generalization a very tricky problem.
As illustrated in Fig. 4.5, a half-quotient of a proper atom might not be essentially 3-connected (but it is
always essentially 2-connected if the proper atom is not a path). Therefore, we would locate Q′ in H which
is not a half-quotient of A. To test it using (P2), we would need to expand some proper atoms and dipoles
in Q′ to reach Q, but it is not clear which ones.
Even more involved is to avoid finding of all quotients Hr = Gr /Γr . Since Hr might consist of many
blocks which might contain many proper atoms and dipoles, it is not clear how to locate it in H to test
existence of a regular covering using (P2).
REFERENCES
[1] J. Abello, M. R. Fellows, and J. C. Stillweil, On the complexity and combinatorics of covering finite complexes,
Australian Journal of Combinatorics, 4 (1991), pp. 103–112.
[2] S. B. Akers and B. Krishnamurthy, On group graphs and their fault tolerance, IEEE Trans. Comput., 36 (1987),
pp. 885–888.
[3] D. Angluin, Local and global properties in networks of processors, in ACM Symposium on Theory of Computing, ACM,
1980, pp. 82–93.
[4] D. Angluin and A. Gardiner, Finite common coverings of pairs of regular graphs, J. Combin. Theory Ser. B, 30 (1981),
pp. 184–187.
[5] L. Babai, Automorphism groups of planar graphs II, in Infinite and finite sets (Proc. Conf. Keszthely, Hungary, 1973)
Bolyai-North-Holland, 1975, pp. 29–84.
, On the isomorphism problem, (1977).
[6]
, Automorphism groups, isomorphism, reconstruction, in Handbook of combinatorics (vol. 2), MIT Press, 1996,
[7]
pp. 1447–1540.
[8]
, Graph isomorphism in quasipolynomial time, in STOC, 2016.
[9] R. Bar-Yehuda and T. Etzion, Connections between two cycles – a new design of dense processor interconnection
networks, Discrete Applied Mathematics, 37–38 (1992), pp. 29–43.
[10] N. Biggs, Algebraic graph theory, Cambridge University Press, 1993.
[11] O. Bı́lka, J. Jirásek, P. Klavı́k, M. Tancer, and J. Volec, On the complexity of planar covering of small graphs, in
WG 2011, vol. 6986 of Lecture Notes in Computer Science, 2011, pp. 83–94.
[12] H. L. Bodlaender, The classification of coverings of processor networks, Journal of Parallel and Distributed Computing,
6 (1989), pp. 166–182.
[13] L. Campbell, Dense group networks, Discrete Applied Mathematics, 37–38 (1992), pp. 65–71.

3 Even

more natural would be to replace (P3) with (P3∗ ), but this problem seems even more tricky.

ALGORITHMIC ASPECTS OF REGULAR GRAPH COVERS

37

[14] L. Campbell, G. E. Carlsson, M. J. Dinneen, V. Faber, M. R. Fellows, M. A. Langston, J. W. Moore, A. P.
Mullhaupt, and H. B. Sexton, Small diameter symmetric networks from linear groups, IEEE Trans. Comput., 41
(1992), pp. 218–220.
[15] G. E. Carlsson, J. E. Cruthirds, H. B. Sexton, and C. G. Wright, Interconnection networks based on a generalization
of cube-connected cycles, IEEE Trans. Comput., 100 (1985), pp. 769–772.
[16] A. Cayley, The theory of groups: Graphical representation, Amer. J. Math., 1 (1878), pp. 174–176.
[17] S. Chaplick, J. Fiala, P. van’t Hof, D. Paulusma, and M. Tesař, Locally constrained homomorphisms on graphs of
bounded treewidth and bounded degree, Theoretical Computer Science, 590 (2015), pp. 86–95.
[18] C. J. Colbourn and K. S. Booth, Linear times automorphism algorithms for trees, interval graphs, and planar graphs,
SIAM J. Comput., 10 (1981), pp. 203–225.
[19] W.H. Cuningham and J. Edmonds, A combinatorial decomposition theory, Canad. J. Math., 32 (1980), pp. 734–765.
[20] P. Erdös, S. Fajtlowicz, and A. J. Hoffman, Maximum degree in graphs of diameter 2, Networks, 10 (1980), pp. 87–90.
[21] S. Evdokimov and I. Ponomarenko, Circulant graphs: recognizing and isomorphism testing in polynomial time, St.
Petersburg Mathematical Journal, 15 (2004), pp. 813–835.
[22] H. M. Farkas and I. Kra, Riemann surfaces, in Riemann Surfaces, vol. 71 of Graduate Texts in Mathematics, 1992,
pp. 9–31.
[23] T. Feder and M. Y. Vardi, The computational structure of monotone monadic snp and constraint satisfaction: A study
through datalog and group theory, SIAM Journal on Computing, 28 (1998), pp. 57–104.
[24] J. Fiala, Note on the computational complexity of covering regular graphs, in 9th Annual Conference of Doctoral Students,
WDS’00, Matfyzpress, 2000, pp. 89–90.
[25] J. Fiala, P. Klavı́k, J. Kratochvı́l, and R. Nedela, Algorithmic aspects of regular graph covers with applications to
planar graphs, in Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014, vol. 8572 of
Lecture Notes in Computer Science, 2014, pp. 489–501.
[26]
, 3-connected reduction for regular graph covers, CoRR, abs/1503.06556 (2016).
[27] J. Fiala and J. Kratochvı́l, Locally constrained graph homomorphismsstructure, complexity, and applications, Computer Science Review, 2 (2008), pp. 97–111.
[28] L. Folwarczný and D. Knop, IV-matching is strongly NP-hard, CoRR, abs/1506.08388 (2015).
[29] O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, in FOCS, vol. 86, 1986, pp. 174–187.
[30] D. M. Goldschmidt, Automorphisms of trivalent graphs, Annals of Mathematics, 111 (1980), pp. 377–406.
[31] J. L. Gross and T. W. Tucker, Topological graph theory, Courier Dover Publications, 2001.
[32] D. Guo, J. Wu, H. Chen, and X. Luo, Moore: An extendable peer-to-peer network based on incomplete Kautz digraph
with constant degree, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE,
2007, pp. 821–829.
[33] Z. Hedrlı́n and A. Pultr, On full embeddings of categories of algebras, Illinois Journal of Mathematics, 10 (1966),
pp. 392–406.
[34] P. Hell and J. Nešetřil, On the complexity of H-coloring, J. Combin. Theory Ser. B, 48 (1990), pp. 92–110.
[35] A. J. Hoffman and R. R. Singleton, On moore graphs with diameters 2 and 3, IBM Journal of Research and Development, 4 (1960), pp. 497–504.
[36] I. Holyer, The np-completeness of edge-coloring, SIAM Journal on Computing, 10 (1981), pp. 718–720.
[37] J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM Journal on Computing, 2
(1973), pp. 135–158.
[38] J. E. Hopcroft and J. Wong, Linear time algorithm for isomorphism of planar graphs (preliminary report), in Proceedings of the sixth annual ACM symposium on Theory of computing, ACM, 1974, pp. 172–184.
[39] C. Jordan, Sur les assemblages de lignes., Journal für die reine und angewandte Mathematik, 70 (1869), pp. 185–190.
[40] M. O. Katanaev, All universal coverings of two-dimensional gravity with torsion, Journal of mathematical physics, 34
(1993), pp. 700–736.
[41] P. Klavı́k, D. Knop, and P. Zeman, Graph isomorphism restricted by lists, CoRR, abs/1607.03918 (2016).
[42] P. Klavı́k, R. Nedela, and P. Zeman, Constructive approach to automorphism groups of planar graphs, CoRR,
abs/1506.06488 (2016).
[43] P. Klavı́k and P. Zeman, Automorphism groups of geometrically represented graphs, in STACS 2015, vol. 30 of LIPIcs,
2015, pp. 540–553.
, Automorphism groups of geometrically represented graphs, CoRR, abs/1407.2136 (2015).
[44]
[45] J. Kratochvı́l, A. Proskurowski, and J. A. Telle, Covering regular graphs, J. Comb. Theory Ser. B, 71 (1997),
pp. 1–16.
[46] D. Lichtenstein, Isomorphism for graphs embeddable on the projective plane, in ACM Symposium on Theory of Computing, STOC ’80, 1980, pp. 218–224.
[47] A. Lubiw, Some NP-complete problems similar to graph isomorphism, SIAM Journal on Computing, 10 (1981), pp. 11–21.
[48] E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System
Sciences, 25 (1982), pp. 42–65.
[49] R. Mathon, A note on the graph isomorphism counting problem, Information Processing Letters, 8 (1979), pp. 131–132.
[50] B. D. McKay, M. Miller, and J. Širáň, A note on large graphs of diameter two and given maximum degree, J. Combin.
Theory Ser. B, 74 (1998), pp. 110–118.
[51] M. Miller and J. Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electronic Journal of
Combinatorics, 61 (2005), pp. 1–63.
[52] S. Negami, The spherical genus and virtually planar graphs, Discrete Mathematics, 70 (1988), pp. 159–168.
[53] G. Ringel and J. Youngs, Solution of the Heawood map-coloring problem, Proceedings of the National Academy of
Sciences of the United States of America, 60 (1968), pp. 438–445.
[54] J.J. Rotman, An Introduction to the Theory of Groups, Graduate Texts in Mathematics, Springer, 1994.

38

J. FIALA, P. KLAVÍK, J. KRATOCHVÍL, R. NEDELA

[55] U. Schöning, Graph isomorphism is in the low hierarchy, Journal of Computer and System Sciences, 37 (1988), pp. 312–
323.
[56] B.A. Trakhtenbrot, Towards a theory of non-repeating contact schemes, Trudi Mat. Inst. Akad. Nauk SSSR, 51 (1958),
pp. 226–269.
[57] W. T. Tutte, Connectivity in graphs, vol. 15, University of Toronto Press, 1966.
[58] J. Šiagiová, A note on the McKay-Miller-Širáň graphs, J. Combin. Theory Ser. B, 81 (2001), pp. 205–208.
[59] T.R.S. Walsh, Counting unlabeled three-connected and homeomorphically irreducible two-connected graphs, J. Combin.
Theory B, 32 (1982), pp. 12–32.
[60] S. Zhou, A class of arc-transitive Cayley graphs as models for interconnection networks, SIAM Journal on Discrete
Mathematics, 23 (2009), pp. 694–714.

