Sequential and parallel algorithms for treewidth-bounded, planar and hierarchically specified combinatorial problems
R. Venkatesh Babu · 1993
This dissertation investigates how the complexity of combinatorial problems relates both to the structure of and to the means of specifying problem instances. We do this for treewidth-bounded, planar and $\delta$-near-planar instances and for hierarchically specified instances. Chapter 2 deals with path problems restricted to instances of bounded treewidth. Let n denote the number of vertices of a graph or the number of variables of a system of linear equations and k denote the treewidth. We give $O(nk\sp2)$ time algorithms for solving a linear system of equations on a field or a closed-semiring and for solving the single-source shortest path problem. We give an $O(n\sp2k)$ time algorithm for the all-pairs shortest path problem. In Chapter 3, algorithms are given for problems for $\delta$-near-planar graphs. (i.e. graphs laid out in the plane with a linear number of crossovers.) Algorithms are given both for polynomial time path problems and for NP-complete optimization problems. In both cases, the asymptotic time bounds of our algorithms match those of the best known bounds for planar graphs. In Chapter 4, we characterize the complexities of the generalized satisfiability problems of Schaefer when instances are specified hierarchically. We show that all such problems which are NP-complete in the non-hierarchical case become PSPACE-complete in the hierarchical case. We also show that all such problems which are in P in the non-hierarchical case remain in P except for the weakly positive and weakly negative satisfiability problems. These latter problems become PSPACE-complete in the hierarchical case. In Chapter 5, we extend the concept of treewidth, to apply to hierarchically specified nonserial optimization problems and to hierarchically specified graphs. We call this concept hierarchical treewidth. For all fixed $k\ge1,$ we show that a large class of nonserial optimization problems and of graph problems can be solved in linear time for hierarchically specified instances of hierarchical treewidth ${\le}k.$ In Chapter 6, we give NC approximation schemes for the problems planar and $\delta$-near-planar 3SAT $(\delta>0).$ Then as corollaries, we give NC approximation schemes, for a number of planar algebraic problems and for a number of planar graph and hypergraph problems.