Cardinality Encodings for Graph Optimization Problems

Alexey Ignatiev, António Morgado, João Marques-SilvaIJCAI 2017 · DOI

TL;DR

This paper tackles the challenge of solving large-scale graph optimization problems (like finding the largest clique) using SAT solvers. The authors introduce a novel, more compact encoding for the maximum clique problem that significantly outperforms existing methods on sparse graphs, making SAT solvers a viable option for these previously intractable problems.

What Problem Does This Paper Address?

Many real-world problems, especially in network analysis, can be modeled as graph optimization problems such as finding the maximum clique, maximum independent set, or minimum vertex cover. These problems are notoriously difficult (NP-hard). While Satisfiability (SAT) and Maximum Satisfiability (MaxSAT) solvers have become powerful tools for solving combinatorial problems, their application to large, sparse graphs has been hindered by inefficient propositional encodings. Existing methods often generate formulas that grow quadratically with the number of vertices, quickly becoming too large for even the most powerful solvers, especially when dealing with the complement graph of sparse networks. This paper aims to bridge this gap by developing more efficient encodings that allow SAT solvers to tackle these problems on large-scale graphs.

Methods

The paper's core contributions lie in identifying inefficiencies in existing encodings and proposing a new one for the maximum clique problem.

  • Identifying Inefficiencies: The authors point out that many existing propositional encodings for graph optimization problems implicitly use "hidden pairwise encodings" to represent cardinality constraints (specifically, AtMost1 constraints). These encodings, when applied to problems like MaxClique on sparse graphs, can lead to a quadratic blow-up in the number of clauses, particularly when considering the complement graph.
  • Novel MaxClique Encoding: For the maximum clique problem, the paper proposes a new encoding that directly uses the original graph's vertices and edges, avoiding the need to analyze the complement graph. This encoding relies on two key cardinality constraints:
  • A global constraint ensuring exactly K vertices are selected for a clique of size K.
  • Local constraints ensuring that if a vertex is selected for the clique, exactly K-1 of its neighbors are also selected. These constraints are then translated into SAT clauses. The authors also discuss practical optimizations, such as filtering vertices that cannot possibly be part of a clique of the target size based on their degree.

Datasets

The paper evaluates its proposed methods on several types of datasets:

  • Community Structure Generators: Networks generated using a benchmark generator for community structure [Lancichinetti et al., 2008].
  • Real-World Networks: A selection of large, sparse networks from sources like SNAP and the Network Repository [Leskovec and Krevl, 2014; Rossi and Ahmed, 2015]. These include collaboration networks (ca-), interaction networks (ia-), retweet networks (rt-), social networks (soc-), technological networks (tech-), and web graphs (web-).
  • Crafted Instances: Small, specifically constructed networks derived from unsatisfiable Pigeonhole Principle (PHPn) formulas. These are designed to be challenging for SAT solvers and have known properties regarding their maximum cliques.

Key Insights and Ideas

  • The "Hidden Pairwise Encoding" Problem: A major insight is that many standard encodings for graph problems are inefficient because they implicitly rely on pairwise constraints for cliques, leading to quadratic complexity. This is particularly problematic for sparse graphs where the complement graph can be dense.
  • Direct Encoding for MaxClique: The most significant idea is the development of a MaxClique encoding that avoids the complement graph. By directly formulating the problem using cardinality constraints on the original graph's structure, the encoding size becomes linear in the number of vertices for sparse graphs, a crucial breakthrough.
  • SAT Solvers as Viable Tools: The paper demonstrates that with the right encoding, SAT solvers can indeed be competitive, and sometimes superior, to specialized graph algorithms for problems like MaxClique on large, sparse networks. This opens up new possibilities for leveraging general-purpose solvers.
  • Iterative SAT Solving for Optimization: The proposed encoding is for a decision problem (does a clique of size K exist?). The authors suggest solving the optimization problem (find the largest clique) by iteratively calling the SAT solver with increasing values of K, combined with techniques for computing lower and upper bounds.

Key Results

The experimental results highlight the effectiveness of the proposed encoding:

  • MaxIS Performance: For Maximum Independent Set, the "edge cover by cliques" approach (an intermediate technique discussed) showed significant clause reduction (up to 70%) compared to standard encodings.
  • MaxClique Performance: The novel SAT-based approach (SATClq) demonstrated strong performance on a variety of benchmarks.
  • It solved 31 out of 35 benchmark instances, outperforming specialized solvers like Cliquer and FMC on certain types of instances, particularly the PHPn-based ones.
  • While highly optimized branch-and-bound solvers like LMC solved all instances, SATClq achieved competitive results and, crucially, tackled instances that were previously considered intractable for SAT-based methods.
  • The SAT solving time was often negligible for collaboration networks, showcasing the efficiency of the encoding.

Limitations and Future Work

  • Limitations:
    • The authors acknowledge that their SATClq prototype is still an initial implementation, and highly optimized specialized solvers like LMC might outperform it on some instances.
  • For certain graph structures (e.g., those with many symmetries), the SAT solver's performance can degrade, suggesting a need for further optimization.
  • The IncMaxCLQ solver was not assessed on larger graphs due to its limitations.
  • Future Work:
    • The paper suggests exploring symmetry breaking techniques to improve SAT solver performance on symmetric instances.
  • Further optimizations to the encoding and solver integration are envisioned.
  • The authors believe their approach can be extended to other decision procedures beyond SAT, such as Constraint Programming (CP), Integer Linear Programming (ILP), and Answer Set Programming (ASP).

Summary updated

BibTeX
@inproceedings{ignatiev2017cardinality,
  author = {Alexey Ignatiev and António Morgado and João Marques-Silva},
  title = {{Cardinality Encodings for Graph Optimization Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/91},
}
Figure