Finding a homotopy base for directed paths in an acyclic graph (Q1099184)

A bilinking in an acyclic graph \(G=(V,A)\) is a pair of vertex-disjoint paths with common end-vertices. A path p' is obtained from another path p by an elementary transformation using a bilinking \(\{p_ 1,p_ 2\}\), if \(p_ 1\) is contained in p and \(p_ 1\) is replaced by \(p_ 2\). A homotopy base of G is a minimal set R of bilinkings in G such that for any two paths p and p' in G with common end-vertices, p' is obtained by repeated elementary transformations using bilinkings in R. A simple characterization of homotopy bases of G is presented and an \(O(| V|^ 2| A|)\) algorithm with \(O(| V| +| A|)\) working space for finding a homotopy base of G is given.