A note on transitive orientations with maximum sets of sources and sinks Original Research Article

Given a transitive orientation G→ of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in G→, respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation G→. A pair of subsets S,T⊆V(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation G→, respectively. We describe algorithms for finding a transitive orientation with a maximum source–sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity.