Maintaining bipartite colourings on temporal graphs on a budget

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 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 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 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 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|E|2^k + nT2^2k) time, and an O(√log(nT))-factor approximation algorithm running in Õ((nT)³) time.

Our results contribute to the structural complexity of networks that change with time with respect to a fundamental computational problem.