Computational Complexity of Covering Regular Trees

The study of graph homomorphisms has a long-standing tradition in combinatorics and theoretical computer science. During the past few decades, numerous variations of the problem have been considered. Informally, graph homomorphism is an adjacency-preserving mapping between two graphs. A significant portion of research in this area focuses on so-called constrained homomorphisms, where additional local or global conditions are imposed on the mapping, such as bijectivity, surjectivity, or injectivity. Among those, the most widely studied are locally bijective homomorphisms, also called graph coverings (or graph lifts). The notion comes from topology, where a covering (also referred to as a covering projection) is a special type of local homeomorphism between topological spaces, and the term of graph covering is basically a discretization of this important and deeply studied concept.

The notion of graph covering quickly proved useful in discrete mathematics, namely as a tool to construct highly symmetric graphs [24, 35, 5, 6, 7, 8] or for embedding complete graphs in surfaces of higher genus [58]. In theoretical computer science, the notion surprisingly found applications in the theory of so-called local computations [2, 16, 17, 18, 23, 50]. In [19], the authors study a close relation of packing bipartite graphs to a special variant of graph coverings called pseudo-coverings.

Despite the efforts and attention that graph covers have received in the computer science community, their computational complexity remains far from being fully understood. Bodlaender [9] proved that deciding if one graph covers another is an NP-complete problem if both graphs are part of the input. The question is obviously at least as difficult as the famous graph isomorphism problem: consider two given graphs on the same number of vertices. Abello, Fellows, and Stillwell [1] later considered the variant of having the target graph, say $H$, fixed and studied the following parameterized problem.

They were the first to raise the question of a complete characterization of the computational complexity of this problem. This initiated a substantial body of research, primarily focusing on graphs without semi-edges (while already in the seminal paper [1] graphs with multiple edges and loops have been considered). This includes proving the polynomial-time solvability of $H$-Cover for connected simple undirected graphs $H$ that have at most two vertices in every equivalence class of their degree partitions [41] (a graph is simple if it contains no loops, no semi-edges and no multiple edges). Furthermore, the complexity of covering $2$-vertex multigraphs was fully characterized in [42], the characterization for 3-vertex undirected multigraphs can be found in [44]. The most general NP-hardness result known so far is the hardness of covering simple regular graphs of valency at least three [25, 43]. More recently, Bílka et al. [15] proved that covering several concrete small graphs (including the complete graphs $K_4,K_5$ and $K_6$) remains NP-hard for planar inputs. This shows that planarity does not help in graph covering problems in general, yet the conjecture that the $H$-Cover problem restricted to planar inputs is at least as difficult as for general inputs, provided $H$ itself has a finite planar cover, remains still open. Planar graphs have also been considered by Fiala et al. [28] who showed that for planar graphs $H$, the so called $H$-RegularCover is in FPT when parameterized by $H$. Let us point out that in all the above results it was assumed that $H$ has no multiple edges, no loops and no semi-edges.

Another connection to algorithmic theory comes through the notions of the degree partition and the degree refinement matrix of a graph. These notions were introduced by Corneil [21, 22] in hope of solving the graph isomorphism problem efficiently. This motivated Angluin and Gardiner [3] to prove that any two finite regular graphs of the same valency have a finite common cover, and conjecture the same for every two finite graphs with the same degree refinement matrix, which was later proved by Leighton [47].

The stress on finiteness of the common cover is natural. For every matrix, there exists a universal cover, an infinite tree, that covers all graphs with this degree refinement matrix. Trees are planar graphs, and this inspired an at first sight innocent question of which graphs allow a finite planar cover. Negami observed that projective planar graphs do (in fact, their double planar covers characterize their projective embedding), and conjectured that these two classes actually coincide [56]. Despite a serious effort of numerous authors, the problem is still open, although the scope for possible failure of Negami’s conjecture has been significantly reduced [4, 39, 40].

As mentioned earlier, the requirement for local bijectivity can be relaxed. In these relaxations, homomorphisms can be either locally injective or locally surjective and not necessarily locally bijective. The computational complexity of locally surjective homomorphisms has been classified completely, with respect to the fixed target graph [34]. Though the complete classification of the complexity of locally injective homomorphisms is still out of sight, it has been proved for its list variant [32]. The problem is also interesting for its applied motivation – the locally surjective version has played an important role in the social sciences [34], particularly in the Role Assignment Problem. A prominent special case of the locally injective homomorphism problem is the well-studied $L(2,1)$-labeling problem [37]. Further generalizations include the notion of $H(p,q)$-coloring, a homomorphism into a fixed target graph $H$ with additional rules on the neighborhoods of the vertices [27, 45]. It is worth noting that for every fixed graph $H$, the existence of a locally injective homomorphism to $H$ is provably at least as hard as the $H$-Cover problem itself. To find more about locally injective homomorphisms, see e.g. [20, 33, 51]. We also refer the reader to the survey concerning various aspects of locally constrained homomorphisms [33].

So far, we have not been speaking about semi-edges, which are informally really just edges with exactly one endpoint (similar to loops, which have a single unique endpoint but are incident twice to that endpoint). Semi-edges appear naturally in group-theoretical and topological constructions where covers are mostly used and employed. Graphs with semi-edges arise as quotients of standard graphs by groups of automorphisms which are semiregular on vertices and darts (arcs) but may fix edges. From the graph-theoretical point of view, semi-edges allow an elegant and unifying description of several crucial graph-theoretical notions. For instance, it was observed before that a simple $k$-regular graph is $k$-edge-colorable if and only if it covers the one-vertex graph with $k$ semi-edges. Similarly, a simple cubic graph contains a perfect matching if and only if it covers the one-vertex graph with one loop and one semi-edge. Last but not least, in modern topological graph theory graphs with semi-edges are widely used and considered since these occur naturally in algebraic graph reductions. Let us name just a few other significant examples of usage of semi-edges. Malnič et al. [52] considered semi-edges during their study of abelian covers to allow for a broader range of applications. Furthermore, the concept of graphs with semi-edges was introduced independently and naturally in mathematical physics [36]. It is also natural to consider semi-edges in the mentioned framework of local computations (we refer to the introductory section of [11] for more details). Finally, a theorem of Leighton [47] on finite common covers has been recently generalized to the semi-edge setting in [59, 60]. To highlight a few other contributions, the reader is invited to consult [53, 55], the surveys [46, 54], and finally for more recent results, the series of papers [28, 30, 29] and the introductions therein.

Surprisingly, the study of the computational complexity of covering graphs with semi-edges is quite young and recent and it was initiated by Bok et al. in [11] in 2021 where the complete complexity dichotomy was established for one- and two-vertex target graphs. Continuing in this direction, Bok et al. [14] studied the computational complexity of covering disconnected graphs and showed that, under an adequate yet natural definition of covers of disconnected graphs, the existence of a covering projection onto a disconnected target graph is polynomial-time decidable if and only if it is the case for every connected component of the target graph. In [13], the authors consider the list version of the problem, called List-$H$-Cover, where the vertices and edges of the input graph come with lists of admissible targets. It is proved that the List-$H$-Cover problem is NP-complete for every regular graph $H$ of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result they show the NP-co/polytime dichotomy for the computational complexity of List-$H$-Cover for cubic graphs $H$. Most recently, Bok et al. [10] presented a complete characterization of the computational complexity of covering colored mixed (multi)graphs with semi-edges whose every class of degree partition contains at most two vertices. That provides a common generalization of the observation for simple graphs from [42], and for the case of regular 2-vertex graphs from [11].

An interesting fact is that all the known NP-hard instances of $H$-Cover remain NP-hard for simple input graphs. This led the authors of [12] to formulate the following conjecture.

In the following subsection, we present our main results, which align well with the Strong Dichotomy Conjecture.

For integers $i$, $j$, the notation $[i,j]$ stands for the set $\{i,i+1,\mathrm{\dots },j\}$. It is an empty set, when $i>j$. We often abbreviate $[1,j]$ by $[j]$.

In this paper we only consider undirected graphs without further stressing this. A simple graph is a pair $G=(V,E)$, where $V$ is a set of vertices and $E\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$ is a set of edges. Edges are viewed as two-element subsets of the vertex set, but for the sake of brevity, we will often write $uv$ as a short-hand notation for $\{u,v\}$. For a graph $G$, we denote its vertex set by $V_G$ and its edge set by $E_G$. Two vertices $u$ and $v$ are called adjacent if $uv\in E_G$. A path in $G$ is a sequence of distinct vertices such that every two consecutive ones are adjacent. A cycle in $G$ is a path that connects two adjacent vertices (the edge between these vertices should not belong to the path, but it belongs to the cycle). A graph is acyclic if it contains no cycles. A graph is connected if any two vertices are joined by a path. A simple tree is a simple connected acyclic graph. The path on $n$ vertices $\{1,2,\mathrm{\dots },n\}$ is denoted by $P_n$.

The (open) neighborhood $N_G(u)$ of a vertex $u\in V_G$ in a simple graph $G$ is the set of all vertices adjacent to $u$. The link neighborhood of $u$ is the set of edges incident with $u$ and we denote it by $N_G^{\prime }(u)$. The degree of $u$ in $G$, denoted by ${\mathrm{deg}}_{G}u$, is the number of vertices adjacent to $u$ (or equivalently the number of edges incident with $u$), formally ${\mathrm{deg}}_{G}u=|N_G(u)|=|N_G^{\prime }(u)|$. If the graph $G$ is clear from the context, we often omit the subscripts and write simply $N(u),N^{\prime }(u)$ and $\mathrm{deg}u$.

In a cubic graph every vertex is of degree 3, while in a subcubic one, every vertex is of degree at most 3.

A covering projection from a simple graph $G$ (guest) to a simple graph $H$ (host) is a mapping $f:V_G\to V_H$ such that for every vertex $u\in V_G$, the restriction ${f|}_{N_G(u)}$ is a bijection between $N_G(u)$ and $N_H(f(u))$.

A partial covering projection is defined analogously, but the restriction ${f|}_{N_G(u)}$ is required to be an injection between $N_G(u)$ and $N_H(f(u))$ for each $u\in V_G$.

In this paper we consider a more general definition of undirected graphs. From now on, a vertex may be connected to itself by a loop (contributing by 2 to its degree), or it might be incident with a semi-edge (an edge-type object having only one end-vertex and contributing by 1 to the degree of this vertex). Moreover, edges, loops, and semi-edges may have associated multiplicities. Next, we present the formal definition. Although we do not work with graphs containing loops in this paper, we provide the definition in this more general form to maintain consistency with other existing literature.

The degree of $u\in V$ is then $\mathrm{deg}u=|\{e\in E:u\in \iota (e)\}|+2|\{l\in L:u=\iota (l)\}|+|\{s\in S:u=\iota (s)\}|$. Each loop is counted twice, as we see it as a topological curve that has both endpoints in $u$. The link-neighborhood corresponding to the links originating from $u$ is $N^{\prime }(u)=\{e\in E:u\in \iota (e)\}\cup \{l\in L:u=\iota (l)\}\times [2]\cup \{s\in S:u=\iota (s)\}$. This choice of link-neighborhood is conform with the above definition of the degree $\mathrm{deg}u=|N^{\prime }(u)|$. A vertex is called semi-simple if it is incident with no loops, with no multiple edges and with at most one semi-edge. Most standard graph-theoretical notions extend naturally from simple graphs to general ones. The graph is called $d$-regular if all of its vertices have degree $d$, and it is called regular if it is $d$-regular for some $d$. Paths and cycles are considered as sequences of links, rather than sequences of vertices. A path is a sequence of edges and semi-edges such that any two consecutive ones share a vertex and all vertices appearing in the path are different; it follows that a path may start and/or end with a semi-edge, but all inner links are normal edges. Such a path is open if it starts and ends with semi-edges, and it is half-open if exactly one of the terminal links is a semi-edge. On top of simple cycles (i.e., cycles in the sense of cycles in simple graphs), any two parallel edges form a cycle of length $2$, and a loop is a cycle of length $1$. No cycle contains any semi-edge. A tree is again defined as a connected acyclic graph. That means that trees have no multiple edges, and no loops, but they may contain semi-edges. A graph is called bipartite if its vertex set can be partitioned into two disjoint sets, each of them being stable in the sense that it contains no links (not even semi-edges).

We say that a graph $G$ covers a graph $H$ if it allows a covering projection from $G$ to $H$.

It also follows from the definition that a covering projection yields, for every vertex $u\in V_G$, a bijective mapping between $N_G^{\prime }(u)$ and $N_H^{\prime }(f(u))$ – one only has to alternate on $l\times [2]$ when mapping a cycle to a loop $l$. Therefore, graph covering projections are also referred to as locally bijective homomorphisms. A partial covering projection loosens the bijection requirement to an injection. It is an incidence preserving mapping $f:G\to H$ such that $N_G^{\prime }(u)$ is mapped injectively into $N_H^{\prime }(f(u))$ for every vertex $u$ of $G$.

When $f$ is a covering projection, then the lift $f^{-1}(x)$ is also referred to as the fiber of (a vertex or a link) $x$.

A direct consequence of the well-known path lifting theorem [57] is that when $G$ covers a connected graph $H$, then fibers of any two vertices in $H$ have the same cardinality. Such a covering is called $k$-fold, where $k$ is the cardinality of the fibers. The path lifting theorem also yields the following statement.

We begin our study by examining paths. (Let us recall that $P_n$ stands for a path on $n$ vertices.) The $P_2^{\uparrow d}$-Cover has been shown to be NP-complete in [11] for all $d\ge 3$. The $P_1^{\uparrow d}$-Cover problem is equivalent to the $d$-edge-colorability of $d$-regular graphs, a problem well known to be NP-complete for every $d\ge 3$ for simple input graphs [48]. Here we focus on covers of graphs $P_n^{\uparrow 3}$ and $C_{2n}^{\uparrow 3}$, depicted in Figure 1.

Since semi-edges can be mapped only onto semi-edges (this holds for every covering), we get the following observations.

In this section we describe an NP-hardness reduction from $3$-Edge-Coloring. The reduction is heavily based on the reduction from [13]. There a more general reduction from $k$-Edge-Coloring is used to show that List-$H$-Cover is NP-complete whenever $H$ is a $k$-regular graph which contains at least one semi-simple vertex, and $k\ge 3$. (We recall that the input of List-$H$-Cover is a graph together with lists of admissible targets for every vertex and link.) In fact, the reduction is such that the inputs constructed are simple graphs and the lists are of a very special format – the lists of edges are general (i.e., equal to ${\mathrm{\Lambda }}_H$) and the lists of vertices are either general (i.e., equal to $V_H$) or single-element (and these are all equal to the chosen semi-simple vertex of $H$). For the special case of 3-regular trees, the reduction goes in almost the same way, only a single vertex gadget will be altered to avoid the usage of lists. In the approach used in [12], the lists were used to guarantee that certain vertices are always mapped onto a chosen semi-simple vertex. We show that under certain assumptions we do not need such a strong tool as lists, but we can guarantee that a certain vertex must map onto some semi-simple one. The claim is relaxed in the sense that we do not know which semi-simple vertex it will be, but nevertheless, the NP-completeness follows.

We use an auxiliary bipartite graph $Q=Q(T,4)$ constructed as follows:

Take four copies of $T$ and denote the vertices in the $i$-th copy by $u_i$, for $u\in V_T$. For every $u\in V_T$ such that ${\mathrm{deg}}_{T}u=1$, form a $C_4$ by adding edges $u_i{u}_{(imod4)+1}$. For every $u\in V_T$ such that ${\mathrm{deg}}_{T}u=2$, add edges of a perfect matching of form $u_i{u}_{i+2}$, see Fig. 5 (c).

We introduce the following notation: We call a vertex $u\in V_T$ relevant (for the hardness reduction) if ${\mathrm{deg}}_{T}u=3$, or if ${\mathrm{deg}}_{T}u=2$ and it has a neighbor $v$ in $T$ such that ${\mathrm{deg}}_{T}v\ge 2$. The vertices which are not relevant are called irrelevant. Irrelevant vertices were already described in Observation 11 as possible images of vertices on a $C_4$. Note that every relevant vertex is semi-simple, but the converse does not need to be true. In $Q$ as well as in $T\times K_2$, a vertex $u_i$ is called (ir)relevant if $u$ is (ir)relevant in $T$.

The polynomial reduction used in the proof of Theorem 19 can be extended to $T^{\uparrow d}$ also for $d=\mathrm{\Delta }\ge 4$, by reducing from $d$-Edge-Coloring of $(d-1)$-uniform hypergraphs. On the other hand, for $d>\mathrm{\Delta }$, there are no relevant vertices in $T^{\uparrow d}$ and hence a new reduction needs to be introduced.

In this paper, we demonstrated that any regular tree with vertices of degree $d\ge 3$ yields an NP-complete graph covering problem even for simple input graphs. Since the 1997/2000 result on NP-hardness of covering simple regular graphs [43, 25], this is the first general NP-hardness theorem on graph covers encompassing a large class of regular target non-simple graphs with more than two vertices. For allowing non-simple target graphs in this theorem, we are paying by requesting them to be acyclic.

As we prove the NP-hardness for simple input graphs, the result provides further confirmation of the Strong Dichotomy Conjecture [13], this time for the case of regular trees as target graphs.

Besides the conjecture, whose proof remains the primary goal, we propose another open question that arises from our results: Suppose that $T$ is a tree of maximum degree $\mathrm{\Delta }$. For $d\ge \mathrm{\Delta }$, denote by $\overline{T^{\uparrow d}}$ a $d$-regular graph obtained from $T$ by adding semi-edges or loops so that every vertex of $\overline{T^{\uparrow d}}$ has degree $d$ (note that $\overline{T^{\uparrow d}}$ is not defined uniquely).