SAT-Solving the Poset Cover Problem
Chih-Cheng Rex Yuan, Bow-Yaw Wang · 2025
Read SAT-Solving the Poset Cover Problem by Chih-Cheng Rex Yuan, Bow-Yaw Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04013.txt.
Description
Chih-Cheng Rex Yuan and Bow-Yaw Wang attack a hard combinatorial puzzle with a logic solver. Their 2025 paper concerns the poset cover problem: given a set of total orders, find the fewest partial orders whose completions cover them all. The problem is known to be NP-complete.
A naive translation into Boolean satisfiability blows up in size. The pair instead build swap graphs, a reduction trick that keeps the encoding lean. Modern SAT solvers then crack instances of fair size with ease. Tests with the Z3 prover on random inputs back the claim. The work shows how a careful encoding can bring a forbidding problem within reach of standard tools.
Catalog record
| CREATOR | Chih-Cheng Rex Yuan, Bow-Yaw Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04013