Arborescences and Shortest Path Trees when Colors Matter
<|reference_start|>Arborescences and Shortest Path Trees when Colors Matter: Color-constrained subgraph problems are those where we are given an edge-colored (directed or undirected) graph and the task is to find a specific type of subgraph, like a spanning tree, an arborescence, a single-source shortest path tree, a perfect matching etc., with constraints on the number of edges of each color. Some of these problems, like color-constrained spanning tree, have elegant solutions and some of them, like color-constrained perfect matching, are longstanding open questions. In this work, we study color-constrained arborescences and shortest path trees. Computing a color-constrained shortest path tree 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 color-constrained arborescences of a directed acyclic subgraph of the original graph. While finding color-constrained arborescence of digraphs is NP-hard in general, we give efficient algorithms when the input graph is acyclic. Consequently, a color-constrained shortest path tree on weighted digraphs having only positive weight cycles can be efficiently computed. Our algorithms also generalize to the problem of finding a color-constrained shortest path tree with minimum total weight. En route, we sight nice connections to colored matroids and color-constrained bases.<|reference_end|>
@article{ardra2024arborescences,
    title={Arborescences and Shortest Path Trees when Colors Matter},
    author={P. S. Ardra, Jasine Babu, Kritika Kashyap, R. Krithika, Sreejith K.
  Pallathumadam and Deepak Rajendraprasad},
    journal={arXiv preprint arXiv:2403.06580},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.06580},
    primaryClass={cs.DS cs.CC cs.DM}
}