Solving Large FPT Problems On Coarse Grained Parallel Machines.

Frank Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon

Abstract: Fixed-parameter tractability (fpt) techniques have recently been successful in solving np-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded tree search phase of fpt algorithms. We apply our methodology to the kvc problem which has important applications, eg in multiple sequence alignments for computational biochemistry. We have implemented our parallel fpt method and application specific ``plug-in'' code for the kvc problem using C and the MPI communication library, and tested it on a network of 10 Sun SPARC workstations. This is the first experimental examination of parallel fpt techniques. In our experiments, we obtain excellent speedup results. Not only do we achieve a speedup of p in most cases, many cases even exhibit a super linear speedup. The latter result implies that our parallel methods, when simulated on a single processor, also yield a significant improvement over existing sequential methods.