Guarantees and limits of preprocessing in constraint satisfaction and reasoning

DOI10.1016/j.artint.2014.06.006zbMath1405.68139arXiv1406.3124OpenAlexW2963390509MaRDI QIDQ460604

Stefan Szeider, Serge Gaspers

Publication date: 13 October 2014

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3124

zbMATH Keywords

computational complexityreasoningconstraint satisfactionfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (4)

Complexity and approximability of parameterized MAX-CSPs ⋮ Meta-kernelization with structural parameters ⋮ On the parameterized complexity of clustering problems for incomplete data ⋮ Backdoors to tractable answer set programming

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Improved upper bounds for vertex cover
• Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints
• Constraint satisfaction with bounded treewidth revisited
• Filtering algorithms for the NValue constraint
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• Tree clustering for constraint networks
• Treewidth. Computations and approximations
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Preprocessing of intractable problems
• Logic programs with stable model semantics as a constraint programming paradigm
• The computational complexity of probabilistic inference using Bayesian belief networks
• On the hardness of approximate reasoning
• Kernelization – Preprocessing with a Guarantee
• Backdoors to Satisfaction
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• On Feedback Vertex Set New Measure and New Structures
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Nondeterminism within $P^ * $
• Autoepistemic logic
• Parameterized Complexity and Kernel Bounds for Hard Planning Problems
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Multiplying matrices faster than coppersmith-winograd
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The complexity of theorem-proving procedures
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Theory and Applications of Satisfiability Testing
• The Problem of Simplifying Truth Functions
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Guarantees and limits of preprocessing in constraint satisfaction and reasoning