A QSAT Benchmark Based on Vertex-Folkman Problems (Student Abstract)

David E. NarváezAAAI 2020 · DOI

Introduction

In the field of automated reasoning, benchmarks serve as the essential metrics for measuring the progress and efficiency of solvers. While the Boolean Satisfiability (SAT) community possesses a diverse and mature library of benchmarks, the Quantified Boolean Formula (QSAT) community—which handles formulas containing both existential ($\exists$) and universal ($\forall$) quantifiers—faces a notable shortage of varied, tunable problem sets.

This paper addresses this gap by introducing a new QSAT benchmark generator based on vertex-Folkman problems from extremal graph theory. These problems are uniquely suited for benchmarking because they are conceptually straightforward yet offer a high degree of mathematical precision and difficulty tuning. Furthermore, they allow for the study of "backbones"—unique satisfying assignments—within a QBF context, a phenomenon previously under-explored in QSAT research.

The Vertex-Folkman Problem

A vertex-Folkman graph, denoted as $F^N(a_1, \dots, a_r; m)$, is a graph with $N$ vertices that satisfies two primary conditions:

  1. Clique Avoidance: The graph does not contain a clique (a fully connected subgraph) of size $m$.
  2. Monochromatic Clique Requirement: For any possible coloring of its vertices using $r$ colors, the graph must contain at least one monochromatic clique of size $a_c$ for some color $c$.

Finding such graphs is a significant challenge in extremal graph theory. By translating these requirements into a logical formula, the author creates a rigorous test for modern QBF solvers.

Methodology and Encoding

The author translates the vertex-Folkman properties into a QBF framework using a structured hierarchy of quantifiers:

  • Existential Variables ($\exists$): These variables represent the edges of the graph. The solver is essentially asked: "Does there exist a graph structure..."
  • Universal Variables ($\forall$): These represent all possible $r$-colorings of the vertices. The formula asserts: "...such that for all possible colorings, the monochromatic clique condition is met."
  • Constraints: The encoding includes clauses to enforce the avoidance of $K_m$ cliques and the presence of monochromatic $K_{a_c}$ cliques.

Symmetry Breaking and the Backbone

One of the primary hurdles in graph-based SAT problems is isomorphism; many different edge configurations represent the same graph, leading to a redundant search space. To mitigate this, the author utilizes the nauty package to implement partial symmetry breaking.

This process is crucial for two reasons: it significantly prunes the search space for the solver, and it ensures that the top-level existential variables possess a unique satisfying assignment (the backbone). This allows researchers to study how the existence of a unique graph solution influences the performance of the universal quantification stage, providing new insights into solver heuristics.

Benchmark Implementation

The paper introduces a benchmark generator that produces instances in the standard QDIMACS and QCIR-14 formats, ensuring compatibility with the majority of modern QSAT solvers.

By leveraging the theorem of Łuczak, Ruciński, and Urbański (2001), the generator can select parameters ($N, a_c, m$) that are mathematically guaranteed to result in specific graph properties. This mathematical grounding allows for a "difficulty knob" that researchers can turn to observe exactly where different solver architectures begin to fail or succeed.

Key Results and Insights

  • Pipeline Success: The author successfully automated the generation of complex graph-theoretical formulas, bridging the gap between extremal graph theory and automated reasoning.
  • Verification: Using model enumerators, the author confirmed that the generated instances indeed possess unique solutions modulo symmetries, validating the theoretical design of the benchmark.
  • Accessibility: By hosting the generator and sample solver runtimes on Zenodo, the author has provided a ready-to-use resource for the QBF community.

Future Directions

As a student abstract, this work lays the foundation for several promising research avenues. The author identifies the need for a deeper theoretical analysis of why these specific Folkman-based formulas are computationally hard. Additionally, the benchmark provides a platform to investigate proof complexity. By comparing the lengths of mathematical proofs generated by solvers when they determine a formula is unsatisfiable, researchers can better understand the impact of different symmetry-breaking rules on solver efficiency. Ultimately, this family of formulas is intended to inspire the development of new QSAT heuristics that can better exploit the structural properties of complex graphs.

Summary updated

BibTeX
@inproceedings{narvaez2020qsat,
  author = {David E. Narváez},
  title = {{A QSAT Benchmark Based on Vertex-Folkman Problems (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7213},
}
Figure