The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs

Jakob Greilhuber, Dániel Marx · 2025

Read The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs by Jakob Greilhuber, Dániel Marx (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-01645.txt.

Description

Jakob Greilhuber and Dániel Marx price a partial graph task in a 2025 paper. A classic frame sorts node sets by how many picked neighbors each node holds. The partial twist lets some nodes break the rule, and asks for a small set that satisfies the most nodes.

The team ask whether the partial task costs the same time as the strict one on narrow graphs. For every fixed rule pair, they pin the exact base of the run time in the graph's width. Upper and lower bounds match under a standard hardness faith. Some rule pairs make the partial task strictly harder. The map completes the cost picture for this family.

Catalog record

CREATORJakob Greilhuber, Dániel Marx
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE171 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel