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

CREATORMatthias Bentert, Fedor V. Fomin, Petr A. Golovach
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE217258
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.00891

Browse the full library · About the Tower of Babel