A Brief Survey of Fixed-Parameter Parallelism

Abstract

This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions. In particular, we present a general view of how known FPT techniques, such as bounded search trees, color coding, kernelization, and iterative compression, can be modified to produce fixed-parameter parallel algorithms.

Keywords

• fixed-parameter parallelism
• parameterized complexity
• parallel computing