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
| CREATOR | Bernardo Subercaseaux ( [email protected] ) |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-14042