On approximating transitivity and tractability of graphs - Manchanda, Saksham, author; McConnell, Ross, advisor; Ray, Indrakshi, advisor; Hulpke, Alexander, committee member (Colorado State University. Libraries, 2016)
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.
Keywords: beta measure; NP complete; perfect graphs; graph theory; approximation algorithms; parametrized algorithms