Complexity and approximability of NP- and pspace-hard optimization problems
MADHAV V. MARATHE · 1995
The main goal of the thesis is to use the graph theoretic structure of problem instances and methods of instance descriptions to design efficient approximation algorithms for classical graph theory and satisfiability problems. The various different classes of graphs considered include planar graphs, grid graphs, unit disk graphs, intersection graphs of circles and graphs drawn in civilized manner. The type of problem instance descriptions considered include standard descriptions, various different methods of hierarchical description and periodic descriptions. We investigate the approximability of problems for geometric intersection graphs, emphasizing unit disk graphs. Using the underlying geometric structure, we devise the first sequential/parallel approximation schemes for a number of graph problems when restricted to geometric intersection graphs including unit disk graphs and graphs drawn in a civilized manner. We then investigate the complexity and approximability for a number of basic problems for arbitrary graphs, planar graphs and unit disk graphs when problem instances are specified hierarchically or periodically. Some of the results obtained include the following. (1) A number of basic problems are PSPACE-hard, even for strongly-1-level-restricted hierarchically specified planar graphs and unit disk graphs. (2) Several problems have a polynomial time approximation algorithm with constant performance guarantees when the instances are specified hierarchically. (3) For level restricted hierarchical instances we show that many of these basic problems have efficient approximation algorithms with performance guarantees which are asymptotically equal to the best known performance guarantee in the flat (non-succinct) case. As corollaries we get polynomial time approximation schemes for a large class of problems for planar instances when specified using level-restricted hierarchical or periodic specifications. The results presented in this thesis answer open questions raised by Orlin, Lengauer & Wagner, and Condon, Feigenbaum, Lund & Shor.