The 2-linkage problem for acyclic digraphs (Q1057282)

The paper solves the problem of finding two disjoint directed paths with prescribed ends in an acyclic digraph. This is accomplished by reducing the problem to one of planarity test of an undirected graph. Necessary and sufficient conditions are given in terms of certain forbidden subdigraphs. As a result, it is shown that if any three cycles of a digraph have a common vertex, then all cycles have a common vertex. A precise structural characterization of digraphs of order n and girth \(g\geq 2n/3\) is given. From this it is shown that any such digraph has at most \(3^{n-g}\) distinct cycles and that a digraph of order n and girth \(g\geq 4\) has at most \(2^{n-g}\) shortest cycles.