Online Dominating Set and Coloring for Geometric Intersection Graphs
Minati De, Sambhav Khurana, Satyam Singh · arXiv (Cornell University) · 2023
We present online deterministic algorithms for minimum coloring and minimum dominating set problems in the context of geometric intersection graphs. We consider a graph parameter: the independent kissing number $ζ$, which is a number equal to `the size of the largest induced star in the graph $-1$'. For a graph with an independent kissing number at most $ζ$, we show that the famous greedy algorithm achieves an optimal competitive ratio of $ζ$ for the minimum dominating set and the minimum independent dominating set problems. However, for the minimum connected dominating set problem, we obtain a competitive ratio of at most $2ζ$. To complement this, we prove that for the minimum connected dominating set problem, any deterministic online algorithm has a competitive ratio of at least $2(ζ-1)$ for the geometric intersection graph of translates of a convex object in $\mathbb{R}^2$. Next, for the minimum coloring problem, we obtain algorithms having a competitive ratio of $O\left({ζ'}{\log m}\right)$ for geometric intersection graphs of bounded scaled $α$-fat objects in $\mathbb{R}^d$ having widths in the interval $[1,m]$, where $ζ'$ is the independent kissing number of the geometric intersection graph of bounded scaled $α$-fat objects having widths in the interval $[1,2]$. Finally, we investigate the value of $ζ$ for geometric intersection graphs of various families of geometric objects.