---
title: "Non-Binary Constraints and Optimal Dual-Graph Representations"
authors:
  - "Gianluigi Greco"
  - "Francesco Scarcello"
doi: ""
url: "https://ijcai.org/proceedings/2003/33"
pdf: "https://ijcai.org/proceedings/2003/0033.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "227-231"
track: ""
keywords:
---

# Non-Binary Constraints and Optimal Dual-Graph Representations

Gianluigi Greco, Francesco Scarcello

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 227-231.

## Abstract

We study the relationships among structural methods for identifying and solving tractable classes of Constraint Satisfaction Problems (CSPs). In particular, we first answer a long-standing question about the notion of biconnected components applied to an "optimal" reduct of the dual constraint-graph, by showing that this notion is in fact equivalent to the hinge decomposition method. Then, we give a precise characterization of the relationship between the treewidth notion applied to the hidden-variable encoding of a CSP and the same notion applied to some optimal reduct of the dual constraint-graph. Finally, we face the open problem of computing such an optimal reduct. We provide an algorithm that outputs an approximation of an optimal tree decomposition, and give a qualitative explanation of the difference between this graph-based method and more general hypergraph-based methods.