Consensus Algorithms for Trees and Strings

This thesis studies the computational complexity and polynomial-time approximability of a number of discrete combinatorial optimization problems involving labeled trees and strings. The problems considered have applications to computational molecular biology, pattern matching, and many other areas of computer science.

The thesis is divided into three parts. In the first part, we study some problems in which the goal is to infer a leaf-labeled tree from a set of constraints on lowest common ancestor relations. Our NP-hardness proofs, polynomial-time approximation algorithms, and polynomial-time exact algorithms indicate that these problems become computationally easier if the resulting tree is required to comply with a prespecified left-to-right ordering of the leaves.

The second part of the thesis deals with two problems related to identifying shared substructures in labeled trees. We first investigate how the polynomial-time approximability of the maximum agreement subtree problem depends on the maximum height of the input trees. Then, we show how the running time of the currently fastest known algorithm for the alignment between ordered trees problem can be reduced for problem instances in which the two input trees are similar and the scoring scheme satisfies some natural assumptions.

The third part is devoted to radius and diameter clustering problems for binary strings where distances between strings are measured using the Hamming metric. We present new inapproximability results and various types of approximation algorithms as well as exact polynomial-time algorithms for certain restrictions of the problems.