| We consider four NP-hard optimization problems on directed acyclic graphs (DAGs), namely, max clique, min coloring, max independent set and min clique cover. It is well-known that these four problems can be solved in polynomial time on transitive DAGs. It is also known that there can be no polynomial O(n1--epsilon)-approximation algorithms for these problems on the general class of DAGs unless P = NP. We propose a new parameter, beta, as a measure of departure from transitivity for DAGs. We define beta to be the number of vertices in a longest path in a DAG such that there is no edge from the first to the last vertex of the path, and 2 if the graph is transitive. Different values of beta define a hierarchy of classes of DAGs, starting with the class of transitive DAGs. We give a polynomial time algorithm for finding a max clique when beta is bounded by a fixed constant. The algorithm is exponential in beta, but we also give a polynomial beta-approximation algorithm. We prove that the other three decision problems are NP-hard even for beta ≥ 4 and give polynomial algorithms with approximation bounds of beta or better in each case. Furthermore, generalizing the definition of quasi-transitivity introduced by Ghouila-Houri, we define beta-quasi-transitivity and prove a more generalized version their theorem relating quasi-transitive orientation and transitive orientation. |
