Complexity thresholds for graph color matching on dense and sparse graphs
Structural Complexity of Matching-Match: Dense and Sparse Graphs
Data Structures and Algorithms
Summary
The paper studies a puzzle where you color the points of a network so that the connections between points match a given pattern of color pairs exactly. The authors find that the difficulty of solving this puzzle depends heavily on the network's structure. For very connected graphs with certain patterns, they provide a fast way to find colorings, but the problem can quickly become very hard when the network structure changes slightly. On simpler networks like lines or cycles, the problem is easier to understand and sometimes fast but counting all possible solutions can still be very difficult.
What this means in practice
- •For network system designers: Determine when exact color pattern matching on network connections is computationally feasible based on network structure to guide system design choices.
- •For algorithm engineers: Focus on tractable graph classes like complete multipartite graphs with precoloring to develop efficient algorithms for color pattern realization problems.
A theory result. No direct application yet.
Authors
Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
Abstract
The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.