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

CREATORChih-Cheng Rex Yuan, Bow-Yaw Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-04013

Browse the full library · About the Tower of Babel