On miniaturized problems in parameterized complexity theory

DOI10.1016/j.tcs.2005.10.003zbMath1087.68034OpenAlexW2165019867MaRDI QIDQ820145

Yijia Chen, Jörg Flum

Publication date: 6 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.003

zbMATH Keywords

parameterized complexitysubexponential algorithmsFagin-definability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Compactors for parameterized counting problems ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Parameterized analysis and crossing minimization problems ⋮ An annotated bibliography on 1-planarity ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Color spanning objects: algorithms and hardness results ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Fixed-parameter decidability: Extending parameterized complexity analysis ⋮ Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules ⋮ VC bounds on the cardinality of nearly orthogonal function classes ⋮ Domination and convexity problems in the target set selection model ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms ⋮ Confronting intractability via parameters ⋮ Pursuing a fast robber on a graph ⋮ On families of categorial grammars of bounded value, their learnability and related complexity questions ⋮ Faster and enhanced inclusion-minimal cograph completion ⋮ Parameterized algorithms for module map problems ⋮ Complexity of independency and cliquy trees ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Covering graphs with few complete bipartite subgraphs ⋮ Practical complexities of probabilistic algorithms for solving Boolean polynomial systems ⋮ Containment relations in split graphs ⋮ Fine-grained parameterized complexity analysis of graph coloring problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Which problems have strongly exponential complexity?
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Linear FPT reductions and computational lower bounds
• Vertex packings: Structural properties and algorithms
• Automata, Languages and Programming
• Algorithms and Data Structures
• On the complexity of \(k\)-SAT