Abstract
In static graphs, bipartite coloring is a fundamental, computationally simple task. However, in temporal graphs—where edges appear and disappear over time—maintaining a valid coloring while minimizing the cost of changing node colors (recolouring) becomes significantly more complex. This paper demonstrates that the Temporal Recolouring (TRec) problem for two colors is NP-hard and provides both approximation and fixed-parameter tractable (FPT) algorithms to address it.
Introduction
Graph coloring is a cornerstone of network conflict resolution. In a static setting, determining if a graph is bipartite (2-colorable) is a linear-time operation. Yet, real-world networks are rarely static. Temporal graphs represent these dynamics as a sequence of snapshots. The challenge arises when we must maintain a valid coloring across these snapshots while minimizing the "recolouring cost"—the total number of times any node changes its color over the network's lifetime.
The Temporal Recolouring (TRec) Problem
The authors formalize the problem as follows: Given a temporal graph $\mathcal{G} = (G_1, G_2, \dots, G_T)$, find a sequence of valid 2-colorings $(c_1, c_2, \dots, c_T)$ that minimizes the total number of color changes across all nodes and time steps. This problem, termed Temporal Recolouring (TRec), seeks to balance the immediate constraint of valid coloring in each snapshot with the global goal of stability (minimizing flips).
Complexity and Hardness
The most significant finding is the "easy-to-hard" jump. While static 2-coloring is trivial ($O(E)$), the temporal version is NP-hard even for a lifetime of just two snapshots ($T=2$). The authors prove this via a reduction from MinUnCut, showing that minimizing color flips is mathematically equivalent to minimizing monochromatic edges in a static partition. Furthermore, the problem is hard to approximate within any constant factor unless the Unique Games Conjecture is false.
Algorithmic Solutions
To address this complexity, the paper proposes two primary algorithmic approaches:
- Approximation Algorithm: By transforming the temporal problem into a static "auxiliary graph," the researchers developed an $O(\sqrt{\log(nT)})$-factor approximation algorithm. This approach maps temporal costs and snapshot constraints into a unified graph cut problem, running in $\tilde{O}((nT)^3)$ time.
- Exact FPT Algorithm: For scenarios where the graph remains relatively connected, the paper offers an exact algorithm using Fixed-Parameter Tractability (FPT). The complexity is tied to $k$, the maximum number of connected components in any snapshot, running in $O(T|E|2^k + nT2^{2k})$. This is efficient when $k$ is small, indicating that the difficulty of TRec is driven by graph fragmentation.
Key Results and Insights
- The MinUnCut Connection: The authors realized that the "cost" of changing a color in time is mathematically analogous to the "cost" of having a monochromatic edge in a static graph.
- Higher Colors: For 3 or more colors, the problem becomes even more restrictive; even determining if a zero-cost coloring exists (where no node ever changes color) is NP-hard.
Conclusion and Future Work
This work highlights that temporal dynamics can fundamentally shift the complexity of "easy" graph problems. While the authors provided a logarithmic approximation, they noted that a constant-factor approximation is likely impossible. Future research directions include refining the approximation for specific types of temporal graphs and exploring $\Delta + 1$ coloring, another "easy" static problem that likely becomes "hard" in the temporal domain.
Summary updated