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.
2016 Summer.
Includes bibliographical references.
Rights Access
beta measure
NP complete
perfect graphs
graph theory
approximation algorithms
parametrized algorithms
Associated Publications