Arborescences and Shortest Path Trees when Colours Matter

Given an edge-colored (directed or undirected) graph, our objective is to find a specific type of subgraph, like a spanning tree, an arborescence, a singlesource shortest path tree, a perfect matching, etc., with constraints on the number of edges of each colour. Some of these problems, like colour-constrained spanning tree, have elegant solutions, and some of them, like colour-constrained perfect matching, are longstanding open questions. 

In this talk, we study colour-constrained arborescences and shortest path trees. Computing a colour-constrained shortest path tree (CC-SPT) on weighted digraphs turns out to be NP-hard in general but polynomial-time solvable when all cycles have positive weight. This polynomial-time solvability is due to the fact that the solution space is essentially the set of all colour-constrained arborescences (CCARB) of a directed acyclic subgraph of the original graph. While finding CC-ARB of digraphs is NP-hard in general, we give an efficient algorithm when the input digraph is acyclic. Our algorithm generalises to the problem of finding a CC-SPT with the minimum total weight. Both our algorithms use a single-source shortest path algorithm and a (minimum cost) maximum flow algorithm as subroutines. By using the algorithm by van den Brand et al. (FOCS 2023) for these subroutines, our algorithms achieve near-linear running time when the edge weights are integral and polynomially-bounded in the size of the graph. Our approach can also be adapted to find the largest common independent set of two generalised partition matroids in near-linear time.