Guarantees and limits of preprocessing in constraint satisfaction and reasoning

DOI10.1016/J.ARTINT.2014.06.006zbMATH Open1405.68139arXiv1406.3124OpenAlexW2963390509MaRDI QIDQ460604FDOQ460604

Authors: Serge Gaspers, Stefan Szeider 

Publication date: 13 October 2014

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)