Tractability, hardness, and kernelization lower bound for and/or graph solution

DOI10.1016/j.dam.2017.07.029zbMath1372.05224OpenAlexW2746989594MaRDI QIDQ2410230

Uéverton dos Santos Souza, Fábio Protti

Publication date: 17 October 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.07.029

zbMATH Keywords

clique-widthtree-widthFPTand/or graphsW[1-hard]W[P-complete]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case, Computing the best-case energy complexity of satisfying assignments in monotone circuits, Succinct certification of monotone circuits, Succinct monotone circuit certification: planarity and parameterized complexity, On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem

Cites Work

• Kernel bounds for path and cycle problems
• Revisiting the complexity of and/or graph solution
• On the model-checking of monadic second-order formulas with edge set quantifications
• Lower bounds on kernelization
• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• New graph classes of bounded clique-width
• A randomized competitive algorithm for evaluating priced AND/OR trees
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• Models for parallel and distributed computation. Theory, algorithmic techniques and application
• Directed hypergraphs and applications
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Handle-rewriting hypergraph grammars
• Kernelization: New Upper and Lower Bound Techniques
• Computationally Related Problems
• On the Optimal Solutions to AND/OR Series-Parallel Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item