Propositional Encodings of Acyclicity and Reachability by Using Vertex Elimination

Masood Feyzbakhsh Rankooh, Jussi RintanenAAAI 2022 · DOI

Abstract

This paper introduces a novel approach to encoding graph constraints—specifically acyclicity and reachability—into standard propositional logic (SAT) using vertex elimination graphs. By leveraging the structural property of "directed elimination width," the authors create compact encodings that allow off-the-shelf SAT solvers to outperform specialized, state-of-the-art graph solvers on sparse networks.

Introduction

Many AI tasks, ranging from automated planning and Bayesian network learning to Answer Set Programming (ASP), rely heavily on graph-based constraints. Systems often need to enforce rules such as acyclicity (ensuring no cycles exist) or reachability (ensuring a path exists between two nodes). Enforcing these in a SAT solver—the primary engine for modern logic-based AI—is notoriously difficult.

Existing approaches typically fall into two categories. Explicit encodings, like transitive closure, translate graph rules into standard logic clauses but often result in a prohibitive $O(V^3)$ number of clauses. Alternatively, specialized solvers like GraphSAT use custom propagators to handle graphs. While fast, these specialized solvers are difficult to maintain and cannot easily benefit from the rapid, year-over-year performance improvements in standard SAT solver technology. This research proposes a "middle way": a compact, explicit encoding small enough to be efficient but standard enough to run on any modern SAT solver.

Methodology: Vertex Elimination Graphs

The core innovation of this work is the application of vertex elimination graphs to SAT encoding.

The Intuition

Consider a graph where vertices are removed sequentially. When a vertex is removed, "shortcut" edges are added between all its incoming and outgoing neighbors to preserve reachability information. This process generates a vertex elimination graph. The efficiency of this method is tied to the Directed Elimination Width ($\delta$), a measure of how "tangled" the graph becomes during this process. For sparse graphs with a low $\delta$, the resulting elimination graph remains relatively small.

Illustration of a base graph (a) and its corresponding vertex elimination graph (b).

Encoding Strategy

Instead of encoding every possible path as in traditional transitive closure, the authors encode only the edges and "triangles" created during the vertex elimination process. They provide specific logical formulas to ensure that any cycle or path in the original graph is reflected in the elimination graph. Because the elimination graph is significantly smaller than a full transitive closure for sparse graphs, the resulting SAT formula is much more manageable, with the number of variables proportional to $O(\delta|V|)$.

Experimental Evaluation

The authors evaluated their methods using two primary benchmarks: 2,000 random benchmark graphs with 200 vertices each (varying in elimination width from 5 to 199) and 108 AI planning instances requiring acyclicity and reachability checks.

Key Results

The vertex elimination method demonstrated significant performance gains, particularly on sparse real-world graphs. On acyclicity tasks, it solved 1,928 instances, outperforming both GraphSAT (1,916) and the transitive closure method (1,881).

Performance comparison between the Vertex Elimination Method and GraphSAT on benchmark instances.

As shown in the performance data, the method often provides orders-of-magnitude speedups when the elimination width is less than 25% of the number of vertices. Furthermore, because the output is a standard list of clauses (CNF), the researchers could utilize Kissat, a state-of-the-art SAT solver, leveraging cutting-edge search optimizations unavailable to specialized graph solvers.

Conclusion and Future Work

While highly effective for sparse graphs, the method faces a "dense graph wall": as the directed elimination width approaches the number of vertices, the encoding size grows, and the advantage over specialized propagators diminishes. Additionally, the efficiency of the encoding depends on the vertex elimination order; while the authors used a successful "minimum degree" heuristic, more sophisticated ordering strategies could yield further improvements. Future research may explore applying these elimination-based encodings to other complex graph properties beyond acyclicity and reachability.

Summary updated

BibTeX
@inproceedings{rankooh2022propositional,
  author = {Masood Feyzbakhsh Rankooh and Jussi Rintanen},
  title = {{Propositional Encodings of Acyclicity and Reachability by Using Vertex Elimination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20530},
}
Figure