Complexity Analysis of someProblems in Planar Graphs, Bounded Tree-Width Graphs, and Planar Point Sets

2010

Ph.D

The focus of this thesis is on the complexity analysis of some computational problems in restricted graph-classes. The problems considered include graph isomorphism, various path problems like reachability, shortest path, and longest path computations. We investigate the space complexity of the graph isomorphism problem for planar graphs. The space complexity of path problems is considered for planar graphs, and k-trees. Another problem studied in the thesis is the clustering problem. One of the main results on graph isomorphism included in the thesis is a log-space algorithm for isomorphism of planar graphs. This settles the complexity of planar graph isomorphism, since hardness for log-space is already known. A log-space algorithm is first described for isomorphism of 3-connected planar graphs, which is then used in the algorithm for planar graph isomorphism. The results on path problems include an improved upper bound for computing the length of a longest path between two designated nodes in a planar DAG. We also present new upper bounds for counting the number of paths between two designated nodes in a planar DAG and in a single-sink DAG, under the promise that these numbers are bounded by a polynomial in the size of the graph. Reachability problem is also studied for directed k-trees and a log-space algorithm is given. Complexity of the shortest and longest path problems for directed acyclic k-trees has been analysed and log-space algorithms are described for these problems. We also give matching log-space hardness results, thereby settling the complexity of these problems for directed k-trees and directed acyclic k-trees respectively. These algorithms are applicable for partial k-trees, which are also known as graphs of tree-width at most k, provided a tree-decomposition for partial k-trees is given as input. The tree-decomposition for k-trees is known to be computable in log-space, but is not known for partial k-trees. Another problem studied in this thesis is the k-means problem. It is a variant of the clustering problem. We prove that the k-means problem is NP-hard when the input is a set of points in two dimensions, and k is part of input. Earlier the hardness was known only for those instances where the number of dimensions is a part of input.