Repository logo

On approximating transitivity and tractability of graphs




Manchanda, Saksham, author
McConnell, Ross, advisor
Ray, Indrakshi, advisor
Hulpke, Alexander, committee member

Journal Title

Journal ISSN

Volume Title


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.


Rights Access


beta measure
NP complete
perfect graphs
graph theory
approximation algorithms
parametrized algorithms


Associated Publications