Abstract:

The focus of this thesis is on the complexity analysis of some computational problems in restricted graphclasses. 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 ktrees. Another problem studied in the thesis is the clustering problem.
One of the main results on graph isomorphism included in the thesis is a logspace algorithm for isomorphism of planar graphs. This settles the complexity of planar graph isomorphism, since hardness for logspace is already known. A logspace algorithm is first described for isomorphism of 3connected 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 singlesink 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 ktrees and a logspace algorithm is given. Complexity of the shortest and longest path problems for directed acyclic ktrees has been analysed and logspace algorithms are described for these problems. We also give matching logspace hardness results, thereby settling the complexity of these problems for directed ktrees and directed acyclic ktrees respectively. These algorithms are applicable for partial ktrees, which are also known as graphs of treewidth at most k, provided a treedecomposition for
partial ktrees is given as input. The treedecomposition for ktrees is known to be computable in logspace, but is not known for partial ktrees. Another problem studied in this thesis is the kmeans problem. It is a variant of the clustering problem. We prove that the kmeans problem is NPhard 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. 