Are dual-graph edges the original constraints?

No. Nodes represent original constraints, while edges express overlap and, in the encoding, tuple compatibility.

What if two constraints share no variables?

They have no direct compatibility edge in the basic dual graph.

Is this the same as a planar graph dual?

No. A planar dual is built from faces of an embedding; the CSP construction is built from overlapping constraint scopes.

AI Glossary / Graphs and symbolic AI / Intermediate

Dual graph

Definition

In constraint satisfaction, a dual graph represents each original constraint as a node and connects two nodes when their constraints share one or more variables. In the associated dual encoding, each node becomes a variable whose possible values are the allowed tuples of its constraint. Edges enforce agreement on shared original variables.

What it means

The usual variable-centered view of a constraint problem emphasizes choices such as room, time, or machine. The dual view emphasizes allowable combinations inside each requirement and how those combinations must fit together.
This is the meaning relevant to the supplied AI glossary context. In other areas of graph theory, dual graph often means the face-based dual of an embedded planar graph. That construction is different. Naming the context prevents a reader from confusing shared-variable compatibility with regions in a graph drawing.

How it works

For each constraint, list its scope: the original variables it involves. Create one dual node for it. Connect two nodes if their scopes overlap, and record which variables they share. For a full dual encoding, use each original constraint's satisfying tuples as the corresponding dual variable's domain.
A pair of chosen tuples is compatible only if it assigns the same value to every shared variable. A solution selects compatible tuples across the graph, from which the participating original-variable values can be recovered. Original variables that appear in no constraint require separate domain handling rather than being silently lost. Tuple domains can be large, so the encoding is not automatically a compact or efficient choice.

Three practical examples

A configuration model represents each allowed component combination as a tuple and checks agreement where requirements mention the same component.
A teaching solver converts a nonbinary constraint problem into binary compatibility constraints to demonstrate alternative representations.
A scheduling analyst inspects which requirements interact through shared time or resource variables, using the dual graph as a structural map.

Think of it this way

Think of several forms that each contain some overlapping fields. Every form can be valid by itself, but shared fields must agree across forms before they describe one consistent case. The analogy captures tuple compatibility. It is limited because constraints can be mathematical relations with enormous implicit tuple sets rather than small printed forms.

Worked example

Let original variables x, y, and z each have domain {0,1}. Constraint C1 requires x != y, so its allowed tuples in order (x,y) are (0,1) and (1,0). Constraint C2 requires y = z, so its tuples in order (y,z) are (0,0) and (1,1).
The dual graph has two nodes, C1 and C2, joined by an edge labeled y. Choosing C1's tuple (0,1) forces C2's y coordinate to equal 1, so its compatible tuple is (1,1). This reconstructs (x,y,z) = (0,1,1). Choosing C1's other tuple (1,0) instead pairs with C2's (0,0), giving (1,0,0).
The pair C1=(0,1), C2=(0,0) is not valid even though each tuple independently satisfies its own constraint: their values for y disagree. There are four raw pairs of dual-domain choices, but only two compatible pairs. This small count demonstrates what the dual edge enforces. With two or more shared variables, agreement must hold on all of them, not just one convenient coordinate.

Illustrative case study

At fictional Rowan Configurations, separately approved component tables are combined into a candidate system. Each table row is allowed locally, but two rows specify different values for the same connector type. A dual-compatibility view makes the disagreement explicit before the combination is accepted.
The team retains the original requirements so reviewers can interpret each tuple. This fictional case illustrates representation and consistency checking, without claiming that the dual encoding is faster than the original solver or that local checks alone establish complete system feasibility.

Common misconceptions and mistakes

Do not confuse the graph's nodes with original variables: in this construction the nodes correspond to constraints. The new dual variables represent whole tuples, not individual scalar choices.
Pairwise compatibility of a selected tuple at every node yields consistent shared assignments, but merely making domains arc-consistent does not generally solve a cyclic CSP. Arc consistency says each remaining value has local support; different supports need not combine into one global solution. Also, listing satisfying tuples can grow exponentially with a constraint's arity, so replacing nonbinary constraints with binary ones does not automatically reduce overall difficulty or memory requirements.

Business use

Businesses can use the dual view to understand interactions among requirements and to compare solver formulations. Keep clear mappings from dual nodes and tuple coordinates to original business variables. Estimate tuple-domain sizes before materializing them. Where a solver supports a powerful native global constraint, replacing it with tables may sacrifice useful propagation. Assess complete solution validity and resource use on representative instances rather than choosing a representation solely because its constraints are binary.

Check your understanding

Two allowed tuples agree on one shared variable but disagree on a second shared variable. Are they compatible in the dual encoding?

Answer: No. They must agree on every shared original variable for the pair to describe a consistent combined assignment.

Related terms

Constraint satisfaction problem
constraint scope
dual encoding
allowed tuple
primal graph
hidden-variable encoding
arc consistency

Learn next

Add a third constraint requiring x = z to the worked example. Connect its dual node to the other two, list its allowed tuples, and check whether any complete tuple selection remains. Explain how the contradiction appears in both original and dual views.

Sources

Samaras and Stergiou, original JAIR research section on Dual Encoding: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/samaras05a-html/node7.html Dechter, original Constraint Networks lecture on nonbinary constraints and dual representations: https://ics.uci.edu/~dechter/courses/ics-275/fall-2022/slides/Chapter9-2022.pdf

Previous: Dual extended Kalman filter Next: Dual norm