Problem Structure and Decomposition

Why Structure Matters

The worst-case complexity of CSP backtracking is O(dⁿ). But most real problems have structure in their constraint graph that allows far more efficient solutions. Exploiting structure is the difference between tractable and intractable.

Independent Subproblems

If the constraint graph is disconnected, each connected component is an independent subproblem.

Speedup calculation: - n variables, each component has n/c variables, c components - Backtracking cost: O(d^(n/c)) per component × c components = O(c · d^(n/c)) - vs. monolithic: O(dⁿ)

Example: n=80 variables, d=2, c=4 components of 20 variables each: - Monolithic: 2⁸⁰ ≈ 10²⁴ steps - Decomposed: 4 × 2²⁰ ≈ 4 × 10⁶ steps

Speedup: ~10¹⁸ × faster

Tree-Structured CSPs

If the constraint graph is a tree (no cycles), the CSP can be solved in O(n · d²) — linear in n, no backtracking required.

TREE-CSP-SOLVER Algorithm

function TREE-CSP-SOLVER(csp) returns solution or failure
    n ← number of variables in csp
    root ← any variable
    X ← TOPOLOGICAL-SORT(variables, root)  // X[1] = root, X[n] = leaves

    // Backward pass: enforce arc consistency from leaves to root
    for j = n down to 2 do
        MAKE-ARC-CONSISTENT(PARENT(X[j]), X[j])
        if it cannot be made consistent then return failure

    // Forward pass: assign root-to-leaves
    assignment ← {}
    for i = 1 to n do
        assignment[X[i]] ← any consistent value from D[X[i]]
        if no such value then return failure  // shouldn't happen if backward pass succeeded
    return assignment

Why No Backtracking Is Needed

After the backward pass (arc consistency from leaves to root), every variable is guaranteed to have at least one value consistent with its parent. The forward pass can therefore assign each variable greedily without backtracking.

Proof sketch: By induction. When assigning X[i], all its children X[j] have domains that are still arc-consistent with whatever value X[i] takes (ensured by MAKE-ARC-CONSISTENT(X[i], X[j]) during backward pass).

Complexity

• Topological sort: O(n)
• Backward arc-consistency pass: n−1 arcs, each O(d²) → O(n · d²)
• Forward assignment: O(n)
• Total: O(n · d²)

Cutset Conditioning

What if the constraint graph has cycles but is “nearly” a tree?

Cycle cutset: A set S of variables whose removal leaves a tree.

Algorithm

1. Find a cycle cutset S (ideally small)
2. For each possible assignment of all variables in S:
   a. Check consistency of the assignment
   b. Remove from domains of remaining variables any values inconsistent with S
   c. Solve the remaining tree-structured CSP with TREE-CSP-SOLVER
   d. If a solution is found, return it combined with the S assignment
3. Return failure

Complexity

• |S| = s, remaining tree has n−s variables
• O(dˢ) assignments of S × O((n−s) · d²) for each tree solve
• Total: O(dˢ · (n−s) · d²) ≈ O(dˢ · n · d²)

Insight: If s is small (say s ≤ 20), this is tractable even for large n.

Example: Australia Map Coloring

Remove SA (the most constrained variable). The remaining graph: WA−NT−Q−NSW−V−T is a tree (after disconnecting T). s=1, so only d=3 assignments of SA to try. Each attempt solves a tree in O(n·d²).

Tree Decomposition

A more general method. Decompose the constraint graph into a tree of subproblems where: - Each node is a megavariable (a cluster of original variables) - Each edge represents shared variables between clusters

Treewidth

The treewidth of a constraint graph is one less than the size of the largest cluster in the optimal tree decomposition.

Tractability threshold: Problems with treewidth w have complexity O(n · d^(w+1)) — polynomial in n for fixed w.

Four-Node GPU Topology

For a 4-GPU ring topology, the constraint graph treewidth is at most 2–3, meaning tree decomposition yields a near-polynomial-time exact solver for configuration CSPs on this hardware.

Decision Flowchart

Does constraint graph have any edges?
├── No → Independent variables, assign greedily
└── Yes → Is it a tree?
    ├── Yes → TREE-CSP-SOLVER, O(n·d²)
    └── No → Is treewidth small?
        ├── Yes (w ≤ ~20) → Tree decomposition, O(n·d^(w+1))
        └── No → Is a small cutset available?
            ├── Yes (|S| ≤ ~20) → Cutset conditioning, O(d^s · n · d²)
            └── No → Backtracking + MAC + MRV + LCV

Connection to Probabilistic Inference

This deep connection means advances in CSP decomposition directly transfer to exact probabilistic inference, and vice versa.