At its simplest, a graph homomorphism is a mapping between two graphs that preserves adjacency: if two vertices are connected in the source graph, their images must be connected in the target graph. While this basic definition underpins much of discrete mathematics, researchers have increasingly focused on locally constrained homomorphisms, where the mapping must also preserve the structure of vertex neighborhoods.
The central quest in this field is to establish "dichotomy theorems"—mathematical lines in the sand that classify every possible target graph $H$ as either yielding a problem that is solvable in polynomial time or one that is computationally intractable (NP-complete or #P-hard).
The Local Constraint Twist
A standard homomorphism allows many vertices to collapse onto one. Locally constrained homomorphisms restrict this behavior by looking at the "local view" from each vertex. As surveyed by Fiala et al., these constraints typically fall into three categories:
- Locally Bijective (Graph Coverings): The mapping must be a bijection between the neighborhood of a vertex $v$ and the neighborhood of its image $f(v)$. This means the local structure is perfectly replicated.
- Locally Injective: The mapping must be injective on neighborhoods, ensuring no two neighbors of $v$ are mapped to the same neighbor of $f(v)$.
- Locally Surjective: The mapping must cover every neighbor of $f(v)$ at least once.
The intuition here is that these constraints force the global mapping to respect the degree and connectivity patterns of the target graph $H$. For example, Fiala et al. demonstrate that even for relatively simple target structures like "Theta graphs" (two vertices joined by three paths), determining the existence of a locally injective homomorphism can be NP-complete depending on the lengths of those paths.
The Strong Dichotomy Conjecture
The most ambitious goal in this area is the Strong Dichotomy Conjecture. This conjecture posits that for any fixed target graph $H$, the problem of deciding if a graph $G$ covers $H$ ($H$-Cover) is either in P or is NP-complete. There is no middle ground of "intermediate" complexity.
Recent work has pushed the boundaries of what we know to be "hard." Bok et al. proved that the $H$-Cover problem is NP-complete even when $H$ is a regular tree—a structure that might intuitively seem simple but becomes intractable when "regularized" with semi-edges (edges with only one endpoint). Similarly, Bok et al. established a complete dichotomy for a class of highly generalized graphs where the target's degree partition blocks are small, using a sophisticated blend of 2-SAT and matching algorithms to identify the tractable cases.
Why These Problems Are Hard
The difficulty of these mappings stems from their relationship to Constraint Satisfaction Problems (CSP). While a simple graph coloring is a type of homomorphism, locally constrained versions add layers of requirements that mimic complex logical constraints.
Golovnev et al. provide evidence that these "right-homomorphism" problems (where the target graph is fixed) are fundamentally as difficult as general CSPs. Their work shows that under the Exponential Time Hypothesis, we cannot solve these problems significantly faster than a brute-force search. This suggests that the "naïve" complexity we observe is not a failure of our algorithms, but an inherent property of the graph structures themselves.
Even when we move from decision problems to counting problems, the dichotomy persists. Cai et al. proved a fundamental dichotomy for counting graph homomorphisms with complex weights, showing that the problem is either solvable in polynomial time or #P-hard. This result is crucial because it connects graph theory to statistical physics, where counting these mappings is equivalent to calculating the partition function of a physical system.
Searching for Tractability
If these problems are generally hard, where does tractability lie? Researchers look for specific structural parameters in the input graphs. However, Köhler et al. found that NP-completeness often persists even when the input graphs have very simple structures, such as bounded path-width.
This forces a shift in focus toward the target graph $H$. By classifying the complexity based on $H$, as seen in the work on semi-edges by Bok et al. and pattern counting in sparse graphs by Bressan and Roth, the field is slowly mapping the "jungle" of graph mappings. The ultimate goal remains a universal characterization: a simple rule that looks at a graph $H$ and immediately tells us how hard it is to map into it.
Key Foundational Work
On the computational complexity of partial covers of Theta graphs (2008) — contributed 6 concept elements to this direction.
Locally constrained graph homomorphisms - structure, complexity, and applications (2008) — contributed 5 concept elements to this direction.
Graph Homomorphisms with Complex Values: A Dichotomy Theorem (2013) — contributed 1 concept elements to this direction.