Weak Three-Linking in Eulerian Dgraphs
Toshihide Ibaraki, Svatopluk Poljak · SIAM Journal on Discrete Mathematics · 1991
Let G be an Eulerian digraph, and $a,b,c$ an ordered triple of its vertices. A polynomial time algorithm of $O( e + n^2 )$ time is presented to decide whether G contains three arc disjoint $ab$-, $bc$-, and $ca$-paths, where e and n are the numbers of arcs and vertices, respectively. The algorithm is based on a structural characterization of minimal infeasible instances of the problem.