Asymptotically Smaller Encodings for Graph Problems and Scheduling

Bernardo Subercaseaux ( [email protected] ) · 2025

Read Asymptotically Smaller Encodings for Graph Problems and Scheduling by Bernardo Subercaseaux ( [email protected] ) (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-2506-14042.txt.

Description

Bernardo Subercaseaux presents a computer science paper, published in 2025, on writing classic graph problems far more compactly for logic solvers. Problems such as vertex cover, independent set, and coloring are usually translated into logical form with a clause for nearly every pair of vertices, which grows fast. Subercaseaux shows a covering result from the early nineteen eighties shrinks that translation well below the standard size.

For dense interval graphs the independent set encoding shrinks even more, and it was applied to a known string compression puzzle. As a side benefit, a published scheduling problem also gets a much smaller encoding. The work explains why a popular preprocessing trick for solvers, adding bounded variables, works as well as it does.

Catalog record

CREATORBernardo Subercaseaux ( [email protected] )
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-14042

Browse the full library · About the Tower of Babel