Introduction
In the field of graph theory, a homomorphism is a structure-preserving mapping between two graphs. Specifically, a mapping from a source graph $G$ to a target graph $H$ is a homomorphism if it preserves adjacency: for every edge $(u, v)$ in $G$, the images of these vertices must form an edge $(f(u), f(v))$ in $H$. A landmark result by Hell and Nešetřil (1990) established a clean complexity dichotomy for the standard $H$-COLOURING problem: it is solvable in polynomial time if $H$ is bipartite, and NP-complete otherwise.
This paper extends this classical framework into the realm of tropical graphs. A tropical graph is a graph where each vertex is assigned a color. A tropical homomorphism must preserve both the edge structure and the vertex colors. The research explores how these additional constraints reshape the computational landscape of graph mappings.
Problem Formulations
The authors distinguish between two primary versions of the tropical homomorphism problem:
- $(H, c)$-COLOURING: Both the target graph $H$ and its specific vertex coloring $c$ are fixed. The input is a colored graph $G$, and the goal is to find a color-preserving homomorphism to $(H, c)$.
- $H$-TROPICAL-COLOURING: The target graph $H$ is fixed, but the coloring of $H$ is provided as part of the input. This version asks if there exists any coloring of $H$ that allows for a homomorphism from the input graph $G$.
Computational Universality and CSPs
A central finding of the paper is that tropical graph homomorphisms are computationally "rich." By adapting constructions from Feder and Vardi, the authors demonstrate that tropical homomorphism problems can capture the full complexity of the class of Constraint Satisfaction Problems (CSPs). Specifically, they prove that for every CSP template $T$, there exists a 2-colored bipartite tropical graph $(H, c)$ such that $(H, c)$-COLOURING is polynomially equivalent to $T$-CSP.
This equivalence implies that if the Feder-Vardi Dichotomy Conjecture holds—stating that every CSP is either in P or is NP-complete—then a similar dichotomy must exist for all fixed tropical graph homomorphism problems.
Complexity Dichotomies in Specific Graph Families
The research provides detailed complexity classifications for several important graph families, revealing surprising "jumps" in difficulty.
Even Cycles
For even cycles $C_{2k}$, the complexity of the $H$-TROPICAL-COLOURING problem depends heavily on the cycle length:
- Polynomial Time: For $k \le 6$ (cycles of length up to 12).
- NP-complete: For $k \ge 24$ (cycles of length 48 and above).
The status of cycles with lengths between 14 and 46 remains an open question, representing a significant gap in the current understanding of cycle complexity.
Trees and Small Bipartite Graphs
The authors also established bounds for small graphs and trees:
- Bipartite Graphs: For any bipartite graph $H$ with $|V(H)| \le 8$, the problem is in P. The first instance of NP-completeness appears at 9 vertices ($H_9$).
- Trees: For trees $T$ with $|V(T)| \le 11$, the problem is in P. An NP-complete tree ($T_{23}$) was identified with 23 vertices.
Methodology and Key Concepts
To derive these results, the authors utilized a variety of reduction techniques, including reductions to 2-SAT for polynomial cases and NAE 3-SAT (Not-All-Equal 3-SAT) for NP-completeness proofs. A key structural concept introduced is the forcing vertex—a vertex whose neighbors all possess distinct colors. Mapping a vertex to a forcing vertex effectively constrains the possible mappings for its entire neighborhood, a property that simplifies the construction of complexity gadgets.
Conclusion and Future Work
While this work provides a robust foundation for tropical graph homomorphisms, several avenues for future research remain. Beyond closing the gap for even cycles, the authors suggest focusing on chordal bipartite graphs. They conjecture that for any chordal bipartite graph $H$ that lacks a specific "claw" structure ($G_1$), the tropical coloring problem is solvable in polynomial time. Such a result would significantly advance the classification of bipartite graph complexities in the tropical setting.
Summary updated