Using Blocks for Constraint Satisfaction

The influence of graph-related properties on constraint satisfaction problems (CSP) has been investigated thoroughly. In this paper, we analyze the impact of a further graph concept on CSPs: biconnected components (blocks). They are an important structure which we exploit for constraint satisfaction in various ways. First, we show that a weaker kind of consistency---k-block-consistency (k-BC)---is sufficient for k-consistency under a certain condition on the used variable ordering which we call prefix-connected. BC can be computed more efficiently than other consistencies, because it is less restrictive. Second, we show that redundancy and inconsistency can be detected on the block level. This remains invariant during BC enforcement, since BC enforcement preserves the block structure. Third, we show that the width k of a graph is bounded by kmax k kmax + 1 where kmax is the maximum width of the block induced subgraphs. 1 Introduction In general, a CSP can be attacked by two strategi..