Graph Algorithms and Approximation

The purpose of this research is to design and analyze discrete algorithms solving hard combinatorial graph problems. Because many of these problems are NP-hard, an exact solution is often not feasible; in such cases approximation algorithms are a viable alternative. In addition to attacking approximation problems that seem to require new strategies, a main goal is to investigate the applicability of design principles developed successfully for traditional discrete optimization problems to comparable tasks occurring in other areas, in particular in Computational Molecular Biology and Operations Research. As problems of very similar combinatorial flavor are found in different areas, it can be expected that many solution methods are extendible as well. For example, previous research has resulted in the comparison method to analyze the approximation of the Maximum Independent Set problem for bounded degree graphs. A bipartite graph is used to compare an optimal solution with a solution found by an approximation algorithm. It can be expected that this method will have many more applications. The research plan includes new approaches to algorithm design applicable to various problems in algorithmic graph theory including Steiner trees and the graph isomorphism problem. Another goal is to study the limits of approximability by polynomial time algorithms. While several spectacular results have been obtained in this area, for many approximation problem the gap between the quality of the approximate solutions obtained in polynomial time and the proven hardness results remains large.