Greedoids from flames

Abstract

A digraph $D$ with $r\in V(D)$ is an $r$-flame if for every $v\in V(D)-r$, the in-degree of $v$ is equal to the local edge-connectivity ${\lambda }_D(r,v)$. We show that for every digraph $D$ and $r\in V(D)$, the edge sets of the $r$-flame subgraphs of $D$ form a greedoid. Our method yields a new proof of Lovász' theorem stating: for every digraph $D$ and $r\in V(D)$, there is an $r$-flame subdigraph $F$ of $D$ such that ${\lambda }_F(r,v)={\lambda }_D(r,v)$ for $v\in V(D)-r$. We also give a strongly polynomial algorithm to find such an $F$ working with a fractional generalization of Lovász' theorem.