Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.10052 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- A directed graph $F$ with a root node $r$ is called a flame if for every vertex $v$ other than $r$ the local edge-connectivity value $λ(r,v)$ from $r$ to $v$ is equal to $\varrho_F(v)$, the in-degree of $v$. It is a classic, simple and beautiful result of Lovász that every digraph $D$ with a root node $r$ has a spanning subgraph $F$ that is a flame and the $λ(r,v)$ values are the same in $F$ as in $D$ for every vertex $v$ other than $r$. However, the complexity of finding the minimum weight of such a subgraph is open. In this paper we prove that this problem is solvable in strongly polynomial time for acyclic digraphs. Besides that, we prove a decomposition result of flames into a chain of smaller flames via edge-disjoint branchings and use this to prove a common generalization of Lovász's above mentioned theorem and Edmonds' classic disjoint arborescences theorem.