2 ARC-DISJOINT PATHS IN EULERIAN DIGRAPHS

Let G be an Eulerian digraph, and let {x(1), x(2)}, {y(1), y(2)} be tw o pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G; {x(1); x(2)}, {y(1), y(2)}) is called feasible if there is a choice of h, i, j, k with {h, i} = { j, k} = {1, 2} such that G has two arc-disjoint x(h) x(i)- and y(j) y(k) -paths. In this paper, we characterize the structure of minimal infeas ible instances, based on which an O(m + n log n) time algorithm is pre sented to decide whether a given instance is feasible, where n and m a re the number of vertices and arcs in the instance, respectively. If t he instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m + n log n)) time.