Arborescences and Shortest Path Trees when Colors Matter
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913441180024832 |
|---|---|
| author | Ardra, P. S. Babu, Jasine Kashyap, Kritika Krithika, R. Pallathumadam, Sreejith K. Rajendraprasad, Deepak |
| author_facet | Ardra, P. S. Babu, Jasine Kashyap, Kritika Krithika, R. Pallathumadam, Sreejith K. Rajendraprasad, Deepak |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06580 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Arborescences and Shortest Path Trees when Colors Matter Ardra, P. S. Babu, Jasine Kashyap, Kritika Krithika, R. Pallathumadam, Sreejith K. Rajendraprasad, Deepak Data Structures and Algorithms Computational Complexity Discrete Mathematics G.2.2 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. |
| title | Arborescences and Shortest Path Trees when Colors Matter |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics G.2.2 |
| url | https://arxiv.org/abs/2403.06580 |