Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor · 2026
Read Incremental Dominating Set by Ilan Doron Arad, Jonathan Gal, Seffi Naor (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-2606-27469.txt.
Description
Doron Arad, Gal, and Naor repair the benchmark for online dominating set problems, where vertices arrive one by one and must be covered as they come. Comparing an online algorithm against an all-knowing offline optimum is hopeless: even a star graph forces a huge competitive ratio. Their incremental model constrains the benchmark itself to the same one-by-one choices the algorithm faces. First results cover vertex-weighted graphs and randomised algorithms, in an algorithms paper published in 2026.
A deterministic algorithm achieves a competitive ratio linear in the maximum degree, and a randomised one brings it down to a squared logarithm of the degree in the reported bounds. The results extend to connected dominating sets through a linear-programming formulation with local connectivity constraints. When each arriving vertex's neighbourhood is known in advance, deterministic algorithms match the polylogarithmic ratios. Matching lower bounds certify optimality up to constant factors.
Catalog record
| CREATOR | Ilan Doron Arad, Jonathan Gal, Seffi Naor |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27469