Parameterized problems complete for nondeterministic FPT time and logarithmic space

DOI10.1109/FOCS52979.2021.00027MaRDI QIDQ6943524zbMATH OpenFDO

Authors Carla Groenland, Jesper Nederlof, Hans L. Bodlaender, Céline M. F. Swennenhuis

Publication date 13 August 2025

Full work available at URL https://dspace.library.uu.nl/handle/1874/420485

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Proceedings, conferences, collections, etc. pertaining to information and communication theory (94-06)

Cited in

(18)

• Constrained and ordered level planarity parameterized by the number of levels
• Space-efficient parameterized algorithms on graphs of low shrubdepth
• The parameterised complexity of integer multicommodity flow
• Structural parameterizations of b-coloring
• XNLP-completeness for parameterized problems on graphs with a linear structure
• On the complexity of problems on tree-structured graphs
• On the hardness of generalized domination problems parameterized by mim-width
• Algorithmic meta-theorems for combinatorial reconfiguration revisited
• List colouring trees in logarithmic space
• XNLP-hardness of parameterized problems on planar graphs
• XNLP-completeness for parameterized problems on graphs with a linear structure
• XALP-completeness of parameterized problems on planar graphs
• Single machine scheduling with precedence constraints and bounded maximum delay value
• Parameterized complexities of dominating and independent set reconfiguration
• Upward and rectilinear planarity are W[1]-hard parameterized by treewidth
• Does subset sum admit short proofs?
• Recognizing 2-layer and outer k-planar graphs
• Designing compact ILPs via fast witness verification

This page was built for publication: Parameterized problems complete for nondeterministic FPT time and logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943524)