I am currently looking for an algorithm to determine whether we can direct every edge (no adding or deleting edges allowed) so that the graph is transitive (meaning that if (x,y) and (y,z) are edges then so is (x,z)).
One way to do it is to use PQ trees as I had an interaction with a professor and this is what he had to say but we are looking for a faster algorithm. When I try to do it myself, my mind keeps looping back to the PQ-tree technique. Each edge is allowed only one direction (if in the underlying undirected graph {a,b} is an edge then exactly one of (a,b) and (b,a) is an edge).
Perhaps there is one algorithm better in tense of toner complexity than the PQ-tree approach, but we can't seem to find it in literature. Do we take it that doing a PQ-tree approach is the best way?
The title of this post is the best I could do in the google search bar. Any help is appreciated.