The parity path problem on some subclasses of perfect graphs

The parity path problem is the problem of finding two paths of different parity between two given vertices. This problem is known to be NP-complete on general graphs. Polynomial algorithms were known for the parity path problem on chordal, planar perfect, interval and circular-arc graphs. In this paper, we give polynomial algorithms for this problem on comparability, cocomparability graphs, and linear algorithms on permutation graphs.