Research map / Learning theory and algorithms / Combinatorial and search optimization
Encoding Constraints as Binary Constraint Networks Satisfying BTP
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of BTP Networks (BCNs satisfying the Broken Triangle Property) as a constraint encoding language, proving circuit-complexity limits, succinctness gains over DNNF and 14 ad-hoc constraints, NP-hardness of minimization, and operation/query tractability.
Problem
Whether a tractable hybrid class of binary constraint networks (BTPN) can encode constraints more succinctly than BCT and other constraint representations, and what its modelling power and complexity are.
Approach
Shows the consistency checker of any conservative AC-solvable BCN class (hence BTPN) has polysize monotone circuits, giving circuit-based separations; builds a BTP binary encoding of DNNF showing BTPN is strictly more succinct than DNNF and the 14 ad-hoc constraints.
Key results
- The consistency checker of BTPN constraints can be computed by polysize monotone circuits, so global constraints such as AllDifferent, permutation, circuit and linear cannot be encoded as polysize BTPN.
- BTPN is strictly more succinct than the DNNF constraint and all 14 ad-hoc constraints discussed in Wang and Yap 2023.
- Minimizing the BCN/BCT/BTPN encoding a constraint is NP-hard (Theorem 3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| encode constraints as BTPNs | BTPN · BTPN constraints | consistency-checker circuit size | Helped |
| encode constraints as BTPNs instead of DNNF | constraint representations · General constraints | succinctness | Helped |
| encode constraints as BTPNs instead of ad-hoc constraint representations | constraint representations · 14 ad-hoc constraints | succinctness | Helped |
| encode permutation, AllDifferent, GCC, or NValue constraints as BTPNs | BTPN · Permutation, AllDifferent, GCC, and NValue constraints | polysize encodability | Hurt |
| encode channelling constraints as BTPNs | BTPN · Channelling constraints | polysize encodability | Hurt |
| encode circuit or cycle constraints as BTPNs | BTPN · Circuit and cycle constraints | polysize encodability | Hurt |
| encode knapsack or linear constraints as BTPNs | BTPN · Knapsack and linear constraints | polysize encodability | Hurt |
| compute disjunctions of BTPNs | BTPN · BTPN operations | computational complexity | Helped |
| compute conjunctions of two BTPNs | BTPN · BTPN operations | computational complexity | Hurt |
| minimize the size of a BTPN encoding | BTPN · BTPN minimization | computational complexity | Hurt |
Surprising findings
- Although BTPN is strictly more succinct than DNNF, it is as powerful as DNNF for operations and queries, with conjunction NP-hard and the negation of a BTPN not polytime.
Limitations
- AC on BTPN is weaker than GAC on the encoded constraint, so GAC needs separate propagators (left for future work).
- Global constraints such as AllDifferent, permutation, circuit and linear cannot be encoded as polysize BTPN.
- Minimal BTPN encoding is NP-hard to compute.
Experimental setup
Baselines: DNNF BCT CFG smart table segmented table MDD regular table
Builds on: Broken Triangle Property BCT (binary constraint tree) DNNF Wang and Yap 2023 succinctness results
Closest papers by meaning
- On the Modelling of Constraints with Tractable Logical Operators (AAAI 2025 · similarity 0.85)
- The Impact of Literal Sorting on Cardinality Constraint Encodings (AAAI 2025 · similarity 0.83)
- On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? (AAAI 2024 · similarity 0.83)
- Breaking Symmetries in Quantified Graph Search: A Comparative Study (AAAI 2025 · similarity 0.83)
- Expressive Power of Deep Homomorphism Networks over Relational Databases (NeurIPS 2026 · similarity 0.82)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.