# A SAT Approach to Clique-Width

arXiv: https://arxiv.org/abs/1304.5498 · HTML: https://mlsanity.com/paper/1304.5498/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [Asymptotically Smaller Encodings for Graph Problems and Scheduling](https://mlsanity.com/paper/2506.14042/) (2025)

## Abstract (arXiv)

Clique-width is a graph invariant that has been widely studied in combinatorics and computer science. However, computing the clique-width of a graph is an intricate problem, the exact clique-width is not known even for very small graphs. We present a new method for computing the clique-width of graphs based on an encoding to propositional satisfiability (SAT) which is then evaluated by a SAT solver. Our encoding is based on a reformulation of clique-width in terms of partitions that utilizes an efficient encoding of cardinality constraints. Our SAT-based method is the first to discover the exact clique-width of various small graphs, including famous graphs from the literature as well as random graphs of various density. With our method we determined the smallest graphs that require a small pre-described clique-width.