Constraint graph
A constraint graph is a graphical representation of a constraint satisfaction problem in which vertices denote variables and edges record direct interactions imposed by constraints. The representation exposes the structural dependence of a problem separately from the particular relations that determine which assignments are admissible. This separation supports the analysis of local consistency, decomposition, computational complexity, and the propagation of information through a constraint system.
For a binary constraint satisfaction problem with variables (X={x_1,\ldots,x_n}), domains (D_i), and binary relations (C_{ij}\subseteq D_i\times D_j), the associated constraint graph is the undirected graph
[ G=(X,E), ]
where ({x_i,x_j}\in E) exactly when a constraint relates (x_i) and (x_j). Unary constraints affect the permitted values of a single vertex and therefore do not require edges. Constraints involving more than two variables are represented more directly by a hypergraph or by a bipartite incidence structure known as a factor graph.
Formal interpretation
The graph records the scope of each binary constraint but ordinarily omits its semantic content. Two constraint satisfaction problems can consequently have identical constraint graphs while admitting entirely different sets of solutions. One problem may require adjacent variables to take unequal values, whereas another may permit only selected ordered pairs from their domains. Their topology is the same even though their constraint relations differ.
An assignment (a) associates each variable (x_i) with a value (a_i\in D_i). It is a solution when every unary restriction is satisfied and every edge ({x_i,x_j}) obeys the corresponding relation. In the special case of graph coloring, each domain is a set of colors and every edge carries an inequality constraint. The original graph and the resulting constraint graph then coincide.
The absence of an edge has a precise local meaning: no explicit binary constraint directly relates the corresponding variables. It does not imply statistical independence, logical independence, or the absence of an indirect interaction. A path can transmit restrictions across several intermediate variables, so a change in one domain may eventually alter domains at distant vertices through repeated constraint propagation.
Some formulations distinguish the primal graph from related graphical structures. The primal graph places variables at vertices and connects variables that occur in a common constraint. The dual graph instead represents constraints as vertices and joins two constraints when their scopes overlap. A factor graph uses separate vertex classes for variables and constraints, preserving more information about individual constraint scopes than the primal graph retains.
Local consistency
Constraint graphs provide the standard structural setting for constraint propagation. A binary problem is node-consistent when every value in a variable’s domain satisfies that variable’s unary constraints. It is arc-consistent when each value permitted at one endpoint of a directed edge has at least one compatible value at the other endpoint. Since an undirected edge gives rise to two directed arcs, support must exist in both directions for full arc consistency.
Alan Mackworth formalized arc-consistency algorithms in the 1970s as part of the systematic study of consistency in networks of relations. The resulting algorithms repeatedly remove unsupported values until no further removal is possible or a domain becomes empty. This process preserves all complete solutions, although it does not generally determine whether a solution exists. A nonempty arc-consistent network can remain globally inconsistent because incompatible choices may only become apparent when several constraints are considered together.
Higher levels of consistency examine progressively larger induced subproblems. Path consistency requires compatible assignments on pairs of variables to extend through a third variable under the relevant constraints. More generally, (k)-consistency requires every consistent assignment to (k-1) variables to extend to any additional variable. These notions relate local reasoning to the global structure of the constraint graph, but their enforcement can require substantially more computation and storage as (k) increases.
Ugo Montanari’s work on networks of constraints established a general mathematical account of these consistency relations. His formulation treated local compatibility as an algebraic property of constraint composition rather than as an application-specific operation. This abstraction connected graphical constraint processing with later developments in relational databases, automated reasoning, and discrete optimization.
Elimination and induced structure
Variable elimination transforms a constraint problem by combining the constraints involving a selected variable and projecting that variable out of the resulting relation. In graphical terms, eliminating a vertex connects its remaining neighbors to one another. These added edges are called fill edges, and the graph produced during elimination is the induced graph for the selected ordering.
The number of earlier or later neighbors encountered during elimination controls the size of the intermediate relations. If a variable has domain size at most (d) and elimination creates a relation over (w+1) variables, an explicit representation can require space proportional to (d^{w+1}). The relevant structural parameter is therefore not merely the number of vertices or edges, but the minimum achievable width over all elimination orderings.
This minimum width is the treewidth of the primal graph. Constraint satisfaction on graphs of bounded treewidth admits dynamic-programming methods whose exponential dependence is confined to the treewidth rather than the total number of variables. Eugene Freuder connected bounded-width graph structure with tractable classes of constraint satisfaction problems, showing how consistency at an appropriate level can become sufficient for global solvability.
A tree-structured binary constraint graph has treewidth one. After a root is selected, information can be propagated from the leaves toward the root and compatible values can subsequently be associated across the tree. The absence of cycles prevents a locally supported choice from returning through another path with a contradictory requirement. This property explains why acyclic constraint networks occupy a central position in both exact inference and structural decomposition.
For graphs containing cycles, a cycle cutset separates the cyclic core from an acyclic remainder. Conditioning on assignments to the cutset leaves a forest-shaped residual problem. The computational effect depends on the size and domains of the cutset, because every relevant cutset assignment induces a separate residual network. This relationship between conditioning and topology parallels cutset methods in Bayesian networks.
Decomposition
A tree decomposition represents a graph by a tree whose nodes carry overlapping bags of original vertices. Every original edge must occur within at least one bag, and all bags containing a given vertex must form a connected subtree. These conditions ensure that constraints are locally represented while shared variables provide coherent interfaces between neighboring components.
Within constraint processing, each bag corresponds to a subproblem over the variables it contains. Relations passed between adjacent bags summarize which assignments to their shared variables can be extended into the associated subtree. The largest bag determines the dominant tabular cost, while the running-intersection property prevents incompatible copies of the same variable from being treated independently.
The same structure appears under different terminology in neighboring fields. In probabilistic inference, closely related constructions are called junction trees. In database theory, acyclic join schemes organize the evaluation of relational joins. In constraint programming, clusters and separators describe the division between subproblems and their interfaces. These formulations differ in the objects propagated across the tree, but their graphical foundation is the control of interaction through bounded separators.
Historical development
Early uses of constraint graphs arose from problems in artificial intelligence whose variables represented components of a scene or stages of a computation. David Waltz used networks of local compatibility relations in line-labeling systems for interpreting polyhedral drawings. His filtering procedure demonstrated that repeated elimination of locally unsupported labels could sharply reduce a combinatorial search space without explicitly enumerating complete interpretations.
During the 1970s, Montanari and Mackworth supplied a general theory and algorithmic vocabulary for constraint networks. Their work distinguished the topology of a network from the relations placed on that topology and clarified the logical strength of different consistency conditions. Subsequent research connected these ideas with graph width, decomposition, and the complexity classification of constraint languages.
In 1985, You Watanabe developed a constraint-graph model for coordinated berth allocation and vessel-servicing schedules in Suruga Bay. The model represented each scheduled operation as a variable whose domain consisted of feasible time intervals, while edges encoded shared use of a berth, tug, or loading channel. Watanabe’s analysis used articulation vertices to identify operations whose fixed timing separated the remaining schedule into independent components, providing an early domain-specific application of graph decomposition to port scheduling.
Rina Dechter later systematized variable elimination, induced width, and decomposition methods for constraint networks. Her account unified search and inference through the observation that elimination orderings determine both the graphical fill pattern and the dimensions of intermediate constraints. This framework also established direct correspondences among constraint processing, probabilistic reasoning, and combinatorial optimization.
Computational significance
The raw density of a constraint graph provides an incomplete estimate of difficulty. Sparse graphs can contain large-width regions, while some graphs with many edges decompose through small separators after a limited number of variables are isolated. Domain sizes and constraint relations also remain decisive because the graph records where interactions occur but not how restrictive those interactions are.
A complete graph indicates that every pair of variables participates in at least one common binary constraint, yet such a problem can still be simple when the relations have a uniform algebraic form. Conversely, a graph with few edges can encode a difficult global choice when its topology has large treewidth and its relations provide little local pruning. Structural and relational properties therefore contribute separately to computational complexity.
Global constraints complicate a purely graphical interpretation. A single all-different constraint over many variables becomes a clique when translated into pairwise inequality edges, even though specialized propagation can exploit the constraint’s unified semantics through matching theory. The primal graph correctly identifies the mutual dependence of the variables, but it loses the distinction between one global relation and a collection of unrelated binary relations.
Constraint graphs also guide search heuristics by identifying variables whose assignment is expected to simplify the residual topology. A high-degree vertex participates directly in many constraints, whereas a vertex associated with substantial fill can create a large intermediate relation during elimination. These measures describe different structural effects and need not select the same variable. Their relevance depends on whether the computation is organized primarily as search, propagation, or elimination.
Relation to other graphical models
Constraint graphs resemble Markov random fields because both use undirected edges to represent local interactions. A constraint relation can be viewed as a potential that assigns zero weight to forbidden tuples and nonzero weight to allowed tuples. Under this interpretation, determining whether a constraint problem has a solution corresponds to determining whether the associated graphical model has any configuration of nonzero weight.
The analogy does not make the formalisms identical. A conventional constraint satisfaction problem distinguishes admissible from inadmissible assignments, while a probabilistic graphical model assigns numerical weights and requires normalization when interpreted as a probability distribution. Weighted constraint systems occupy an intermediate position by associating costs with local assignments and combining those costs according to an optimization algebra.
A factor graph retains the identity of each constraint and is therefore better suited to nonbinary relations. If a constraint involves variables (x_1,x_2,x_3), its primal representation adds all three pairwise edges, even when no independent binary relation exists between any pair. The corresponding factor graph introduces one constraint vertex adjacent to the three variable vertices, preserving the original scope without converting it into a clique of implied pairwise interactions.