Linear algorithms for parity path and two path problems on circular-arc graphs (Q4028893)

[For the entire collection see Zbl 0753.00021.] A graph \(G\) is called a circular-arc graph if it is the intersection graph of a family of circular arcs around a circle. Presented is a method for solving path problems in proper circular-arc graphs, that is, circular-arc graphs where no arc is properly contained in another arc. In particular, the method solves these problems for circular-arc graphs: (1) the parity path problem, or finding two chordless paths--an even path and an odd path--between two nonadjacent vertices in a connected graph; (2) the two path problem, or finding two vertex-disjoint paths between designated pairs among four distinct vertices. The key procedure is applying a reduction process to the given family AF of arcs to obtain a new family AF\('\) of arcs for which there is now a vacant interval in the circle. The latter is therefore an interval graph. The authors then cite existing linear algorithms for solving both types of problems on interval graphs.