A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach · 2026
Read A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs by Matthias Bentert, Fedor V. Fomin, Petr A. Golovach (2026) 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-2604-00891.txt.
Introduction
Bentert, Fomin, and Golovach build a framework for subexponential algorithms on planar graphs, covering problems earlier toolkits missed: those with weights, directed graphs, or disconnected solutions. Building on Nederlof's result, it handles weights and allows many connected components. It also covers cases where solution patterns explode with the parameter. They apply it to weighted problems like Weighted Partial Vertex Cover and Maximum-Weight Induced Forest, previously unsolved in this time. An easy-to-use fragment also yields a subexponential algorithm for weighted Densest k-Subgraph.
Catalog record
| CREATOR | Matthias Bentert, Fedor V. Fomin, Petr A. Golovach |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 217258 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00891