AbstractArikati, Pandu Rangan, and Manacher (BIT, 31 (1991) 182-193) developed an O(m+n) algorithm to find two vertex disjoint paths in a circular arc graph on n vertices and m edges. We provide an improved solution to this problem: the algorithm presented here is both faster (O(n) time complexity) and simpler than the previous algorithm. The method involves reductions to interval graphs. In an interval graph, the critical notions are {\em unordered paths} (vertex disjoint paths from s1,s2 to t1,t2 in either order) and interchangeable paths (existence of both pairs of vertex disjoint paths). We also prove a theorem (which is best possible, in a sense), that guarantees existence of vertex disjoint paths, if arcs are sufficiently dense. Finally, we show that the more general problem of determining the existence of k vertex disjoint paths (from s1,...,sk to t1,...,tk) is NP-complete, where k is part of the input, even restricted to the class of interval graphs.
Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: vertex disjoint paths, circular arc graphs, interval graphs, NP-complete
Selected references
- Elaine M. Eschen and Jeremy P. Spinrad. An O(n^2) algorithm for circular-arc graph recognition. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 128-137, Austin, Texas, 25-27 January 1993.
- Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, February 1980.
- Martin Charles Golumbic and Peter L. Hammer. Stability in circular arc graphs. Journal of Algorithms, 9(3):314-320, September 1988.
- Sumio Masuda and Kazuo Nakajima. An optimal algorithm for finding a maximum independent set of a circular-arc graph. SIAM Journal on Computing, 17(1):41-52, February 1988.
- Yossi Shiloach. A polynomial solution to the undirected two paths problem. Journal of the ACM, 27(3):445-456, July 1980.