Towards Work-Efficient Parallel Parameterized Algorithms

Max Bannach, Malte Skambath*, Till Tantau

*Corresponding author for this work


Parallel parameterized complexity theory studies how fixed-parameter tractable (fpt) problems can be solved in parallel. Previous theoretical work focused on parallel algorithms that are very fast in principle, but did not take into account that when we only have a small number of processors (between 2 and, say, 1024), it is more important that the parallel algorithms are work-efficient. In the present paper we investigate how work-efficient fpt algorithms can be designed. We review standard methods from fpt theory, like kernelization, search trees, and interleaving, and prove trade-offs for them between work efficiency and runtime improvements. This results in a toolbox for developing work-efficient parallel fpt algorithms.

Original languageEnglish
Title of host publicationWALCOM 2019: WALCOM: Algorithms and Computation
EditorsGautam K. Das, Partha S. Mandal, Krishnendu Mukhopadhyaya , Shin-ichi Nakano
Number of pages13
Volume11355 LNCS
PublisherSpringer, Cham
Publication date21.12.2018
ISBN (Print)978-3-030-10563-1
ISBN (Electronic)978-3-030-10564-8
Publication statusPublished - 21.12.2018
Event13th International Conference and Workshop on Algorithms and Computations
- Guwahati, India
Duration: 27.02.201902.03.2019
Conference number: 224069

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science


Dive into the research topics of 'Towards Work-Efficient Parallel Parameterized Algorithms'. Together they form a unique fingerprint.

Cite this