Maintaining Bipartite Colourings on Temporal Graphs on a Budget

Duncan Adamson, George B. Mertzios, Paul G. Spirakis

TL;DR

In static graphs, checking if you can color a map with two colors (bipartite coloring) is a trivial undergraduate exercise. This paper reveals that in temporal graphs—where edges flicker in and out of existence over time—maintaining that coloring while minimizing the number of times you "flip" a node's color is surprisingly NP-hard and even difficult to approximate.

What Problem Does This Paper Address?

Graph coloring is the bread and butter of conflict resolution in networks. If two computer processes need the same resource, you give them different "colors" to ensure they don't clash. But real-world networks aren't static; they are temporal. Connections appear and disappear over a sequence of time steps (snapshots).

The authors tackle the Temporal Recolouring (TRec) problem: Given a graph that changes over time, can we find a valid coloring for every snapshot such that the total number of color changes (the "recolouring cost") stays within a certain budget?

While finding a 3-coloring is famously hard even on static graphs, 2-coloring (bipartite coloring) is usually easy. The researchers wanted to know: Does the "easiness" of bipartite coloring carry over to the temporal world? The answer is a resounding "no."

Methods

The paper employs a mix of complexity theory and algorithmic design:

  • Hardness Reductions: To prove the problem is difficult, the authors reduce it from MinUnCut (the problem of partitioning a graph to minimize edges within a group). They show that even a temporal graph with only two snapshots and simple paths is enough to make the problem NP-hard.
  • Auxiliary Graph Construction: For their approximation algorithm, they transform the temporal problem into a static one. They create a massive "auxiliary graph" where each node represents a vertex at a specific time step. Edges in this graph represent either snapshot constraints (must have different colors) or temporal costs (changing color between $t$ and $t+1$).
  • Dynamic Programming: For the exact algorithm, they use a technique called Fixed-Parameter Tractability (FPT). They focus on the number of connected components ($k$) in each snapshot, building a cost table that tracks the best way to color the graph as time progresses.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets or training sets. Instead, it relies on mathematical constructions and worst-case analysis to prove the limits of what algorithms can do.

Key Insights and Ideas

  • The "Easy-to-Hard" Jump: The most striking insight is that adding a temporal dimension turns a linear-time problem ($O(E)$ for static bipartite coloring) into one that is not only NP-hard but also hard to approximate within any constant factor (assuming the Unique Games Conjecture).
  • 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. This allowed them to borrow powerful approximation tools from the world of static graph cuts.
  • Component-Driven Complexity: They found that the difficulty isn't necessarily the number of nodes ($n$) or the lifetime ($T$), but how "fragmented" the graph is. If each snapshot has only a few connected components, the problem becomes solvable in a reasonable amount of time.

Key Results

  • Hardness: Proved that 2-color TRec is NP-hard even for a lifetime of $T=2$. Furthermore, it is hard to approximate within any constant factor unless the Unique Games Conjecture is false.
  • Approximation Algorithm: Developed an algorithm that provides an $O(\sqrt{\log(nT)})$-factor approximation. This means the solution found is at most a logarithmic factor worse than the absolute best possible solution. It runs in $\tilde{O}((nT)^3)$ time.
  • Exact FPT Algorithm: Provided an exact algorithm that runs in $O(T|E|2^k + nT2^{2k})$ time, where $k$ is the maximum number of connected components in any snapshot. This is efficient if $k$ is small (e.g., the graph stays mostly connected).
  • Higher Colors: Showed that for 3 or more colors, even determining if a zero-cost coloring exists (where no node ever changes color) is NP-hard.

Limitations and Future Work

The primary limitation is the approximation gap. While the authors provided a logarithmic approximation, they noted that a constant-factor approximation is likely impossible.

Future research directions include:

  1. Refining the Approximation: Can we get closer to a constant factor for specific types of temporal graphs?
  2. Temporal Matchings: The authors suggest looking at graphs where each snapshot is just a "matching" (disjoint edges), which might be easier to solve.
  3. $\Delta + 1$ Colouring: Exploring if similar approximation factors can be achieved for general graphs using more colors (specifically, one more than the maximum degree), which is another "easy" problem in the static world that likely becomes "hard" in the temporal one.

Summary updated

Abstract

Graph colouring is a fundamental problem for networks, serving as a tool for avoiding conflicts via symmetry breaking, for example, avoiding multiple computer processes simultaneously updating the same resource. This paper considers a generalisation of this problem to \emph{temporal graphs}, i.e., to graphs whose structure changes according to an ordered sequence of edge sets. In the simultaneous resource updating problem on temporal graphs, the resources which can be accessed will change, however, the necessity of symmetry breaking to avoid conflicts remains. In this paper, we focus on the problem of \emph{maintaining proper colourings} on temporal graphs in general, with a particular focus on bipartite colourings. Our aim is to minimise the total number of times that the vertices change colour, or, in the form of a decision problem, whether we can maintain a proper colouring by allowing not more colour changes than some given \emph{budget}. On the negative side, we show that, despite bipartite colouring being easy on static graphs, the problem of maintaining such a colouring on graphs that are bipartite in each snapshot is NP-Hard to even approximate within \emph{any} constant factor unless the Unique Games Conjecture fails. On the positive side, we provide an exact algorithm for a temporal graph with $n$ vertices, a lifetime $T$ and at most $k$ components in any given snapshot in $O(T \vert E \vert 2^{k} + n T 2^{2k})$ time, and an $O\left(\sqrt{\log(nT)}\right)$-factor approximation algorithm running in $\tilde{O}((nT)^3)$ time. Our results contribute to the structural complexity of networks that change with time with respect to a fundamental computational problem.
BibTeX
@inproceedings{adamson2026maintaining,
  author = {Duncan Adamson and George B. Mertzios and Paul G. Spirakis},
  title = {{Maintaining Bipartite Colourings on Temporal Graphs on a Budget}},
  booktitle = {SIROCCO},
  year = {2026},
  doi = {10.1007/978-3-032-26465-7\_2},
}
Figure