

J. Cheetham, F. Dehne, A. RauChaplin, U. Stege, P. J. Taillon 

Abstract: Fixedparameter tractability (FTP) techniques have recently been successful in solving NPcomplete 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 boundedtree search phase of FTP algorithms. We apply our methodology to the kVertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FTP method for the kVertex Cover problem using C and the MPI communication library, and tested it on a 32 node Beowulf cluster. This is the first experimental examination of parallel FTP techniques. As part of our experiments, we solved larger instances of kVertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k > 400 in less than 1.5 hours. 

paper.pdf 

