On approximating transitivity and tractability of graphs
Date
2016
Authors
Manchanda, Saksham, author
McConnell, Ross, advisor
Ray, Indrakshi, advisor
Hulpke, Alexander, committee member
Journal Title
Journal ISSN
Volume Title
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.
Description
2016 Summer.
Includes bibliographical references.
Includes bibliographical references.
Rights Access
Subject
beta measure
NP complete
perfect graphs
graph theory
approximation algorithms
parametrized algorithms