Path Consistency on Triangulated Graphs

39 concepts17 papers

In constraint satisfaction problems (CSPs) and graphical models, ensuring that a network of variables is logically consistent is a vital preprocessing step. As shown in GSAT and Local Consistency, enforcing local consistency on structured problems can transform previously intractable instances into trivial ones.

Among local consistency techniques, Path Consistency (PC) is one of the most powerful. It dictates that for any pair of variables $(x, z)$, the direct relation between them must be compatible with the indirect relation via any third variable $y$.

Historically, enforcing path consistency came with a massive computational penalty: it required a fully connected graph. If two variables did not share an explicit constraint, traditional algorithms forced the addition of a "universal" relation (meaning any value pair is allowed) to complete the graph. As Bliek observes in Path Consistency on Triangulated Constraint Graphs, this completion process inflates the number of constraints quadratically relative to the number of variables, resulting in excessive memory consumption and a cubic ($O(n^3)$) time complexity.

This dense representation directly undermines the topological sparsity of real-world problems. Decades ago, Dechter et al. (Removing Redundancies in Constraint Networks) demonstrated that simplifying a problem's connective structure by removing redundant edges allows search algorithms to perform significantly larger jumps across the search space. The core challenge, then, is to enforce path consistency without destroying graph sparsity.

The solution is Partial Path Consistency (PPC) executed over triangulated (chordal) graphs.

The Intuition: Propagation via Triangles

To understand why we can avoid full graph completion, consider the structural property of a chordal graph. A graph is chordal, or triangulated, if every cycle of four or more nodes contains a chord—an edge connecting two non-adjacent nodes in the cycle. This means the entire graph can be viewed as a collection of interconnected triangles.

Traditional Full Completion:          Chordal Triangulation:
       A ----------- B                       A ----------- B
       | \         / |                       | \           |
       |   \     /   |                       |   \         |
       |     X       |                       |     \       |
       |   /     \   |                       |       \     |
       | /         \ |                       |         \   |
       D ----------- C                       D ----------- C
  (Forces all pairs, O(n^3))            (Only local triangles needed)

In a fully completed graph, a path consistency algorithm must check every possible triplet $(x, y, z)$. However, if a graph is triangulated, we only need to enforce path consistency on triplets that form actual triangles within the graph.

Why is this sufficient? Imagine a four-node cycle $A-B-C-D-A$ without a direct edge between $A$ and $C$. If we triangulate the graph by adding the chord $(A, C)$, we split the cycle into two triangles: $\triangle ABC$ and $\triangle ACD$.

  1. Enforcing path consistency on $\triangle ABC$ refines the relation along the chord $(A, C)$ based on the paths through $B$.
  2. Enforcing path consistency on $\triangle ACD$ then propagates this refined information to $D$.

Because the chord acts as an information conduit, the network achieves global consistency across the cycle without ever needing to explicitly compute or maintain a direct relation between $B$ and $D$. As Long et al. demonstrate in Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks, restricting checks to the edges of a chordal triangulation allows for efficient reasoning in sparse networks while completely bypassing the cubic complexity wall.

Why It Works: The Equivalence of Local and Global Pruning

The reason this restriction works without sacrificing inferential power comes down to a mathematical equivalence. For specific, well-behaved classes of constraints, enforcing consistency solely over a triangulated graph yields the exact same pruning results on the original edges as running full path consistency on a completed graph.

Convex Constraints

Bliek (Path Consistency on Triangulated Constraint Graphs) proved that for convex constraint satisfaction problems, the extra edges added during full graph completion are entirely redundant for pruning purposes. The essential structural information required to propagate local consistency is fully captured by the triangulation. Even in general non-convex discrete constraints, partial path consistency on triangulated structures retains nearly all the pruning capacity of full completion.

Distributive Subalgebras

This principle is heavily exploited in Qualitative Spatial and Temporal Reasoning (QSTR), where datasets can scale into millions of objects. The authors of On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi and Efficiently Characterizing Non-Redundant Constraints in Large Real World Qualitative Spatial Networks showed that for distributive subclasses of relations, local consistency maintained over a chordal graph is mathematically equivalent to global path consistency. Triangulation allows local consistency checks to propagate across the network, facilitating the identification and removal of redundant, implied relations without requiring a dense representation.

Broad Applications Across Domains

The strategy of bounding consistency checks by graph topology appears across several distinct domains:

  • Difference Logic and Verification: In hardware verification, Bryant et al. (Deciding Separation Formulas with SAT) applied chordal graph triangulation to reduce the number of transitivity constraints needed for SAT encodings. By only enforcing constraints on small local triangles, they significantly reduced clause generation while maintaining full logical correctness.
  • Linear Programming Relaxations: When optimizing high-order graphical models, standard Linear Program (LP) relaxations can become intractable if they enforce consistency across all variable interactions. Rowland et al. (Conditions beyond treewidth for tightness of higher-order LP relaxations) showed that higher-order constraints can be restricted to those appearing in a chordal triangulation or envelope without sacrificing the exactness of the solution. Similarly, Weller (Characterizing Tightness of LP Relaxations by Forbidding Signed Minors.) demonstrated that for specific graph classes, the full set of triplet constraints can be replaced by a much smaller set of signed cycle inequalities.
  • High-Order Potentials: Mezuman et al. (Tighter Linear Program Relaxations for High Order Graphical Models) showed that enforcing consistency on a carefully selected tree-structured subset of edges is often sufficient to reach a global optimum while maintaining tractability.
  • Network Partitioning: In temporal reasoning, Li et al. (A Divide-and-Conquer Approach for Solving Interval Algebra Networks) optimized SAT encodings by enforcing path consistency only within localized partitions of the constraint graph, ignoring triangles that span across different partitions to keep the encoding size proportional to the graph's actual connectivity.

Conclusion

Partial path consistency on triangulated graphs bridges the gap between theoretical pruning power and practical execution. By recognizing that global consistency propagates through local triangles, these algorithms scale based on the graph's elimination degree rather than the total number of variables (Zhang). Whether applied to spatial databases, hardware verification, or machine learning optimization, chordal triangulation ensures we only compute the relationships that matter.

Key Foundational Work

Removing Redundancies in Constraint Networks (1987) — contributed 1 concept elements to this direction.
GSAT and Local Consistency (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_partial_path_consistency_8c611dd0,
  title = {partial path consistency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-path-consistency/rdr_8c611dd0ffb1450486918a6e8b649337},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_partial_path_consistency_8c611dd0_v1,
  title = {partial path consistency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/partial-path-consistency/rdr_8c611dd0ffb1450486918a6e8b649337/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake