Guarantees and limits of preprocessing in constraint satisfaction and reasoning

DOI10.1016/J.ARTINT.2014.06.006MaRDI QIDQ460604zbMATH OpenOpenAlexFDO

Authors Serge Gaspers, Stefan Szeider

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 complexityconstraint satisfactionfixed-parameter tractabilitykernelizationreasoning

Mathematics Subject Classification ID

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

Abstract: We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning under structural restrictions. All these problems involve two tasks: (i) identifying the structure in the input as required by the restriction, and (ii) using the identified structure to solve the reasoning task efficiently. We show that for most of the considered problems, task (i) admits a polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, in contrast to task (ii) which does not admit such a reduction to a problem kernel of polynomial size, subject to a complexity theoretic assumption. As a notable exception we show that the consistency problem for the AtMost-NValue constraint admits a polynomial kernel consisting of a quadratic number of variables and domain values. Our results provide a firm worst-case guarantees and theoretical boundaries for the performance of polynomial-time preprocessing algorithms for the considered problems.

Recommendations

• Artificial Intelligence: Methodology, Systems, and Applications
• A synthesis of constraint satisfaction and constraint solving
• Publication:3489503
• scientific article; zbMATH DE number 1759450
• Beyond Q-resolution and prenex form: a proof system for quantified constraint satisfaction
• An exact algorithm for the constraint satisfaction problem: Application to logical inference
• Methods and Applications of Artificial Intelligence
• scientific article; zbMATH DE number 1234562
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 5547867 (Why is no real title available?)
• scientific article; zbMATH DE number 1319354 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2084707 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A kernelization algorithm for \(d\)-hitting set
• Autoepistemic logic
• Backdoors to satisfaction
• Constraint satisfaction with bounded treewidth revisited
• Exact exponential algorithms.
• Filtering algorithms for the NValue constraint
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Handbook of constraint programming.
• Handbook of knowledge representation.
• Improved upper bounds for vertex cover
• Introduction to algorithms.
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Kernelization -- preprocessing with a guarantee
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Logic programs with stable model semantics as a constraint programming paradigm
• Multiplying matrices faster than coppersmith-winograd
• Nondeterminism within $P^ * $
• On feedback vertex set new measure and new structures
• On problems without polynomial kernels
• On the hardness of approximate reasoning
• Parameterized complexity and kernel bounds for hard planning problems
• Preprocessing of intractable problems
• Principles and Practice of Constraint Programming – CP 2004
• Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• The Problem of Simplifying Truth Functions
• The complexity of theorem-proving procedures
• The computational complexity of probabilistic inference using Bayesian belief networks
• Theory and Applications of Satisfiability Testing
• Tree clustering for constraint networks
• Treewidth. Computations and approximations
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(9)

• Backdoors to tractable answer set programming
• Preprocessing of intractable problems
• Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
• Preprocessing of min ones problems: a dichotomy
• On the parallel parameterized complexity of MaxSAT variants
• On the parameterized complexity of clustering problems for incomplete data
• Discovering implied constraints in precedence graphs with alternatives
• Meta-kernelization with structural parameters
• Complexity and approximability of parameterized MAX-CSPs

Describes a project that uses

Uses Software

• MiniSat

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

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