| dc.description.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. | |
