ON THE RELATIVE SIGNIFICANCE OF KERNELIZATION VERSUS BRANCHING FOR PARALLEL FPT IMPLEMENTATIONS

We investigate the relative significance of kernelization versus branching for parallel FPT implementations. Using the well-known vertex cover problem as a familiar example, we build and experiment with a testbed of five different classes of difficult graphs. For some, we find that kernelization alone obviates the need for parallelism. For others, we show that kernelization and branching work in synergy to produce efficient implementations. And yet for others, kernelization fails completely, leaving branching to solve the entire problem. Structural graph properties are studied in an effort to explicate this trichotomy. The NP-completeness of vertex cover makes scalability an extreme challenge. We mainly employ Hopper, named after the famous computing pioneer Admiral Grace Murray Hopper. The Hopper platform is currently one of the world's fastest supercomputers.