On approximating transitivity and tractability of graphs

Abstract

In the general case, in a simple, undirected graph, the problems of finding the largest clique, minimum colouring, maximum independent set and minimum vertex cover are NP-hard. But, there exists some families of graphs, called perfect graphs, where these problems become tractable. One particular class of perfect graphs are the the underlying undirected graphs of transitive digraphs- called comparability graphs. We define a new parameter β to approximate the intransitivity of a given graph. We also use β to give a measure of complexity of finding the largest clique. As β gets worse, the complexity of finding the largest clique quickly grows to exponential times. We also give approximation algorithms that scale with β for all our NP-hard problems. The β measure of a graph can be computed in O(mn), therefore, β can be considered a measure of how tractable these problems are in a graph.