Graph Covers of Bounded-Degree, Tree-Like Graphs: Closing the Treewidth-plus-Degree Question

A graph cover is a map from a large graph $G$ onto a smaller graph $H$ that looks like an isomorphism around every vertex. Each vertex's neighbors are sent one-to-one onto the neighbors of its image. A role assignment relaxes this: every neighbor of the image must be hit at least once, but some may be hit more than once. Both are "locally constrained homomorphisms." They model how network nodes can be grouped into roles, and they are a discrete version of covering spaces in topology.

Deciding whether such a map exists is NP-hard in general. It stays hard even when $G$ looks tree-like: An Algorithmic Framework for Locally Constrained Homomorphisms shows that when $H$ is part of the input, both problems are para-NP-complete parameterized by the treewidth, pathwidth, tree-depth or feedback vertex set number of $G$. Para-NP-complete means NP-hard even when the parameter is a constant. Treewidth measures how close a graph is to a tree. That paper's positive result needs the fracture number, which is much more restrictive and is large on paths, grids and road networks. The authors explicitly leave open the natural middle ground: are covers and role assignments fixed-parameter tractable (FPT) when $G$ has both small treewidth and small maximum degree? FPT means solvable in time $f(k)\cdot n^{O(1)}$ for parameter $k$.

This note proposes to settle that question through one structural statement. The statement is a "transfer lemma": if $G$ locally surjects onto $H$ and $G$ has treewidth $t$ and maximum degree $\Delta$, then $H$ also has bounded structure. The proposal then builds and measures the resulting algorithm, extended to counting, on real low-treewidth networks.

Core Claim

The obstacle to tree-decomposition dynamic programming here is not the degree. The obstacle is that $H$ is unbounded, so a table indexed by assignments of bag vertices to $V(H)$ has $|V(H)|^{O(t\Delta)}$ rows. That is polynomial for fixed parameters, but not FPT. Squaring $G$ removes the degree problem by putting every closed neighborhood inside a bag. This is the easy part.

The hard part is the host. Surjectivity already forces $\Delta(H) \le \Delta(G)$, so the host has bounded degree for free. The proposal's claim is that bounded treewidth also transfers. Bulteau et al. found a "structural bridge" for deletion sets: a small deletion set in $G$ forces one in $H$. We conjecture its treewidth analogue, $\mathrm{tw}(H) \le g(t,\Delta)$ for some function $g$, when $G$ covers or locally surjects onto $H$.

Combined with an anchoring argument, this would allow tables indexed by host vertices relative to a local frame rather than by absolute host labels. That would give an FPT algorithm in $t+\Delta$. If the lemma is false, the proposal pursues the counterexample family as the gadget source for a W[1]-hardness proof. Either outcome resolves the open problem.

The same tables carry counts, which gives the first structural-parameter results for counting covers. The literature here has a dichotomy for weighted homomorphism counting with fixed targets (Cai, Chen, and Lu) and degeneracy-based pattern counting (Bressan and Roth). Neither treats locally constrained maps.

Relation to Prior Work

The motivating work is Bulteau et al. (2022, 2024; An Algorithmic Framework for Locally Constrained Homomorphisms). They prove the tree-like hardness results, give an FPT algorithm via Integer Linear Programming (ILP) over fracture number, and pose the treewidth-plus-degree question. We keep their setting, where both $G$ and $H$ are input, and their surjectivity-driven transfer idea. We replace deletion sets with tree decompositions, which their ILP cannot handle.

Their result that the locally injective variant is W[1]-hard even by $|V(G)|$ constrains our scope. Injective maps let host degrees be unbounded, so no transfer is possible. We therefore exclude that variant deliberately rather than treat it as future work.

Tight Lower Bounds on Graph Embedding Problems gives Exponential Time Hypothesis lower bounds for unconstrained homomorphism and subgraph isomorphism. It asks whether these survive bounded treewidth and degree 3. That paper supplies the hardness toolkit for the negative branch of our program. Our problem differs because local bijectivity is a much stronger constraint than edge preservation, so its reductions do not apply directly.

Bok et al. (2026) constrains the design in a useful way. Covering semi-simple $k$-regular targets is NP-complete even for simple bipartite inputs. Bounded degree and bounded degeneracy alone therefore cannot suffice, and treewidth must do real work. This also tells us that any positive result must fail once semi-edges are allowed and treewidth is unbounded, which serves as a sanity check on the proofs.

On the structural-parameterization side, Paulusma, Slivovsky, and Szeider show that counting can be easier than deciding under modular treewidth. That is a reminder to check separately whether counting covers is harder than deciding them. Eiter, Hecher, and Kiesel show that naive encodings of cyclic constraints into SAT inflate treewidth. This motivates comparing our direct dynamic program against encodings rather than assuming encodings preserve structure.

Research Program

Analytic program. The first step proves the easy half: an algorithm running in $|V(H)|^{O(t\Delta)}\cdot n$ time on a tree decomposition of $G^2$, the square of $G$, where vertices within distance two are joined. The square has treewidth at most $(t+1)(\Delta+1)-1$, so every local bijectivity or surjectivity constraint is checkable within a bag. This algorithm is the explicit floor, and it also counts solutions.

The second step attacks the transfer lemma. We first work for covers of connected $G$, where fibers have equal size and the map has a well-defined degree. We then turn to role assignments. The route is to push a tree decomposition of $G$ through the map and bound how many fibers a pushed bag can meet, using bounded degree to control distortion. The third step converts a bounded-structure host into FPT tables. Given an anchor vertex and its local bijection, bag states are described by paths in $H$ of length bounded by the bag's diameter, so the number of states depends only on $t$ and $\Delta$.

If the lemma resists, the fallback is to look for counterexamples. These would be families of bounded-degree, bounded-treewidth graphs locally surjecting onto hosts of growing treewidth, such as covers of grid-like quotients. Such families become gadgets for a reduction from multicolored clique.

Computational program. The computational program tests the lemma before we try to prove it. On real low-treewidth guests, we will enumerate quotient hosts arising from equitable partitions, which are exactly the targets that admit covers or role assignments. For each we record $\mathrm{tw}(H)/\mathrm{tw}(G)$. A ratio that grows with instance size at fixed $\Delta$ would be strong evidence against the lemma and would point to the hardness branch.

Baselines

The naive reference point is the squared-decomposition algorithm described above. It runs dynamic programming over a tree decomposition of $G^2$ with states indexed by absolute host labels. It is the simple approach any reviewer would propose, and it is correct. Our FPT algorithm must beat it on hosts with many vertices; on tiny hosts the two coincide. Both use the same decomposition heuristic and the same time limit. Beating it means solving instances where $|V(H)|^{\text{bag size}}$ exceeds memory, with runtime flat in $|V(H)|$ at fixed $t,\Delta$.

The strongest general-purpose competitor is a CNF encoding of the local constraints. One Boolean variable says that $v$ maps to $h$. There is one exactly-one constraint per vertex and per neighborhood bijection. The encoding is solved by SharpSAT-TD for counting and by a SAT solver for decision. Shaw and Meel identify SharpSAT-TD as the strongest compilation counter (Model Counting in the Wild). It solved 811 of 1080 non-projected instances on their suite, and the virtual best solver reached 2106 of 2262. These figures are context for solver strength, not a result on our task. There is no reported result found on Lacuna for locally constrained homomorphism decision or counting on any benchmark.

As an alternative encoding we also run clingo, following the solver comparisons in Eiter et al. Fairness requires the same machines, the same wall-clock limit, and inclusion of SharpSAT-TD's own decomposition preprocessing in its time. Beating this baseline means more instances solved, or a growing speedup as $|V(H)|$ grows at fixed $t$.

The ILP over fracture number from Bulteau et al. is the strongest structural method. We will report each guest's fracture number to show where that ILP is even applicable. On networks where it is small, we run it as a direct competitor.

The ablation that isolates the key ingredient is our dynamic program with relative-frame states disabled, falling back to absolute labels. This separates the gain due to the transfer argument from engineering. A second ablation swaps the decomposition of $G^2$ for one of $G$ with neighborhood counters. This tests whether squaring is needed in practice.

Why not just…?

Why not just run tree-decomposition dynamic programming on the square of $G$? It works, and we use it as our floor, but it is only XP: the table grows as $|V(H)|^{O(t\Delta)}$. The open question from Bulteau et al. is precisely whether this exponent can be removed. The comparison against the absolute-label ablation measures whether our relative states matter on real hosts or only in theory. If real hosts are tiny, this alternative suffices in practice, and we will say so.

Why not just encode into SAT and use a model counter? This is the real empirical threat, because modern counters already exploit treewidth internally. Two concerns point the other way. Eiter et al. found that encodings of cyclic constraints can inflate treewidth. The exactly-one neighborhood constraints of our encoding join host variables across whole fibers, so the incidence graph's treewidth may scale with $|V(H)|$ rather than with $t$. We will measure the treewidth of the encoded formulas directly. If it stays bounded and SharpSAT-TD matches us, the empirical case for a dedicated algorithm collapses, leaving only the theoretical result.

Why not just use the fracture-number ILP? It is FPT, but it requires a small vertex set whose removal leaves only constant-size pieces. Paths, cycles and road-like transport networks fail this. Reporting the fracture numbers of the benchmark guests will show directly whether it applies to them.

Why not just parameterize by degeneracy? Bok et al. show covering is NP-complete on bipartite 3-regular inputs, which have degeneracy at most 3. Degeneracy therefore cannot be the right parameter.

Proposed Experiments

Guests come from the PACE 2016/2017 public-transport networks, which have low-to-moderate treewidth and were used by Eiter et al. We use the bounded-degree cores of these networks, and synthetic random lifts of small cubic and 4-regular graphs. In the random lifts a cover is known to exist, and the number of covers can be checked against brute force on small cases. Hosts come from equitable partitions of each guest for positive instances, and from perturbed partitions for negative ones. This yields hosts from five vertices up to a constant fraction of $|V(G)|$.

We measure instances solved within the time limit, runtime as a function of $|V(H)|$ at fixed $t$ and $\Delta$, and agreement of exact counts across all methods.

The decisive checks are three. The first is the treewidth-ratio study: does $\mathrm{tw}(H)/\mathrm{tw}(G)$ stay bounded over all enumerated quotients? This decides which branch of the analytic program to pursue. The second is the scaling of the encoded formulas' treewidth with $|V(H)|$, which decides whether the SAT baseline is structurally handicapped. The third is whether our runtime stays flat in $|V(H)|$ while the absolute-label ablation's runtime grows. This is the empirical signature of the FPT claim.