On Some Algorithmic and Structural Results on Flames

ABSTRACT A directed graph with a root node is called a flame if for every vertex other than the local edge‐connectivity value from to is equal to , the in‐degree of . It is a classic, simple and beautiful result of Lovász [4] that every digraph with a root node has a spanning subgraph that is a flame and the values are the same in as in for every vertex other than . However, the complexity of finding the minimum weight of such a subgraph is open [3]. 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 edge‐disjoint branchings via a chain of smaller flames and use this to prove a common generalization of Lovász's above mentioned theorem and Edmonds' classic disjoint arborescences theorem.