On the space and circuit complexity of parameterized problems: classes and completeness

DOI10.1007/s00453-014-9944-yzbMath1312.68099OpenAlexW2044535619MaRDI QIDQ2343093

Michael Elberfeld, Till Tantau, Christoph Stockhusen

Publication date: 4 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9944-y

zbMATH Keywords

completenessparameterized complexityspace complexitylongest common subsequence problemfeedback vertex set problemassociative generability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (13)

Multistage graph problems on a global budget ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ A parameterized view on the complexity of dependence logic ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Unnamed Item ⋮ The parameterized space complexity of embedding along a path ⋮ Computing Hitting Set Kernels By AC^0-Circuits ⋮ Some lower bounds in parameterized \(\mathrm{AC}^{0}\) ⋮ Problems hard for treewidth but easy for stable gonality ⋮ Parameterised counting in logspace ⋮ Unnamed Item ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits

Cites Work

• Parameterized complexity and approximability of the longest compatible sequence problem
• Advice classes of parametrized tractability
• Complete problems for deterministic polynomial time
• On the parameterized complexity of short computation and factorization
• Describing parameterized complexity classes
• Parametrized complexity theory.
• On non-determinacy in simple computing devices
• Completeness Results for Parameterized Space Classes
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• On Some Deterministic Space Complexity Problems
• An Optimal Parallel Algorithm for Formula Evaluation
• On Linear Time Minor Tests with Depth-First Search
• New problems complete for nondeterministic log space
• Nondeterminism within $P^ * $
• Analogs & duals of the MAST problem for sequences & trees
• On the Space Complexity of Parameterized Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: On the space and circuit complexity of parameterized problems: classes and completeness