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
| CREATOR | Jakob Greilhuber, Dániel Marx |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 171 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01645