Parameter-bounded parallelism for fixed parameter tractable problems

Abstract

Fixed-parameter tractability (FPT) addresses computational hardness by isolating complexity to a problem-specific parameter. As input sizes grow, so does the need for parallelism, partic- ularly when resources are constrained. Current parameterized parallel complexity classes often assume unbounded process counts, leading to inefficient or unpredictable workloads when the process count is limited. This paper introduces Bounded-Process Parallel FPT (BPP-FPT) as a class of parallel FPT algorithms with polynomial runtime in the input size and process count bounded by a function of the parameter. We demonstrate the feasibility of this class with BPP-FPT algorithms for Vertex Cover, Feedback Vertex Set, and Longest path, and show that problems solvable by a bounded search tree of parameter-dependent depth can be par- allelized into a BPP-FPT algorithm. Analysis of the work and process efficiency, including computational overhead and process overprovisioning, establishes lower bounds for BPP-FPT work. Finally, we propose solutions to the efficiency trade-offs of this new class of algorithms and discuss ways to optimize resource allocation and preprocessing time. This work addresses a gap in the current models of parameterized parallel complexity theory and provides a practical framework for developing parallel FPT algorithms under realistic resource constraints.