We survey the use of fixed-parameter algorithms in the field of phylogenetics, which is the study of evolutionary relationships. The central problem in phylogenetics is the reconstruction of the evolutionary history of biological species, but its methods also apply to linguistics, philology or architecture. A basic computational problem is the reconstruction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype like color or form of limbs, based on differences in the genotype like mutated nucleotide positions in the DNA sequence, or based on given partial phylogenies. Ideally, one would like to construct socalled perfect phylogenies, which arise from a very simple evolutionary model, but in practice one must often be content with phylogenies whose ‘distance from perfection’ is as small as possible. The computation of phylogenies has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics often are NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.

We examine classes of distributional problems defined in terms of polynomial-time decision algorithms with bounded error probability. The class AvgP (Levin, 1984) has been characterized by Impagliazzo (1995) using polynomial-time algorithm schemes with benign faults. The class HP extends AvgP by allowing malign faults instead of benign faults. The class AvgHP in turn extends HP by allowing running times to be polynomial on average instead of bounded by a polynomial. Polynomial-time algorithms that decide membership for words of length n with an error probability less than F(n) for some function F lead to the classes F(n)-ErrP (Schindelhauer and Jakoby, 1999). The class dist-nearly-P = /spl cap//sub k/spl ges/1/(1/n/sup k/)-ErrP is an instance of the 'nearly'-classes as introduced by Yamakami (1997). We call a distribution /spl mu/ fair if /spl mu/(n) /spl ges/ 1/p(n) for some polynomial p(n). We prove: 1) The inclusion AvgP /spl sube/ HP is strict. 2) AvgHP equals HP. 3) Problems from HP with fair distributions are in dist-nearly-P. One cannot substantially improve this result. There are problems in AvgP with fair distributions which are not in (1/g(n))-ErrP for every super-polynomial function g(n). And there are problems in AvgP with /spl mu/(n) = 1/g(n) for a super-polynomial function g(n) which are not in dist-nearly-P.

We study the problem of finding a path between two vertices in finite directed graphs whose independence number is bounded by some constant k. The independence number of a graph is the largest number of vertices that can be picked such that there is no edge between any two of them. The complexity of this problem depends on the exact question we ask: Do we wish only to tell whether a path exists? Do we also wish to construct such a path? Are we required to construct the shortest one? Concerning the first question, we show that the reachability problem is first-order definable for all k and that its succinct version is $\Pi_2^{\mathrm{P}}$-complete for all k. In contrast, the reachability problems for many other types of finite graphs, including dags and trees, are not first-order definable, and their succinct versions are PSPACE-complete. Concerning the second question, we show not only that we can construct paths in logarithmic space, but that there even exists a logspace approximation scheme for this problem. The scheme gets a ratio r > 1 as additional input and outputs a path that is at most r times as long as the shortest path. Concerning the third question, we show that even telling whether the shortest path has a certain length is NL-complete and thus is as difficult as for arbitrary directed graphs.

The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets---i.e., the amount of Karp--Lipton advice needed for polynomial-time machines to recognize them in general---the best current upper bound is quadratic [K. Ko, J. Comput. System Sci., 26 (1983), pp. 209--221] and the best current lower bound is linear [L. Hemaspaandra and L. Torenvliet, Theoret. Comput. Sci., 154 (1996), pp. 367--377]. We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound (which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective, then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P = NP. We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.