3.7.9. Alpha-acyclic constraint network(2)

Before defining alpha-acyclic constraint network(2) we first need to introduce the following notions:

  • The dual graph of a constraint network 𝒩 is defined in the following way: to each constraint of 𝒩 corresponds a vertex in the dual graph and if two constraints have a non-empty set S of shared variables, there is an edge labelled S between their corresponding vertices in the dual graph.

  • An edge in the dual graph of a constraint network is redundant if its variables are shared by every edge along an alternative path between the two end points [Dechter89].

  • If the subgraph resulting from the removal of the redundant edges of the dual graph is a tree the original constraint network is called α-acyclic [Fagin83].

Alpha-acyclic constraint network(2) denotes an α-acyclic constraint network such that, for any pair of constraints, the two sets of involved variables share at most two variables.