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

CREATORIlan Doron Arad, Jonathan Gal, Seffi Naor
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel