Title: Improved Bounds for Online Dominating Sets of Trees,
Abstract: The online dominating set problem is an online variant of the minimum
dominating set problem, which is one of the most important NP-hard problems on
graphs. This problem is defined as follows: Given an undirected graph $G = (V,
E)$, in which $V$ is a set of vertices and $E$ is a set of edges. We say that a
set $D \subseteq V$ of vertices is a {\em dominating set} of $G$ if for each $v
\in V \setminus D$, there exists a vertex $u \in D$ such that $\{ u, v \} \in
E$. The vertices are revealed to an online algorithm one by one over time. When
a vertex is revealed, edges between the vertex and vertices revealed in the
past are also revealed. A revelaed subtree is connected at any time.
Immediately after the revelation of each vertex, an online algorithm can choose
vertices which were already revealed irrevocably and must maintain a dominating
set of a graph revealed so far. The cost of an algorithm on a given tree is the
number of vertices chosen by it, and its objective is to minimize the cost.
Eidenbenz (Technical report, Institute of Theoretical Computer Science, ETH
Zürich, 2002) and Boyar et al.\ (SWAT 2016) studied the case in which given
graphs are trees. They designed a deterministic online algorithm whose
competitive ratio is at most three, and proved that a lower bound on the
competitive ratio of any deterministic algorithm is two. In this paper, we also
focus on trees. We establish a matching lower bound for any deterministic
algorithm. Moreover, we design a randomized online algorithm whose competitive
ratio is at most $5/2 = 2.5$, and show that the competitive ratio of any
randomized algorithm is at least $4/3 \approx 1.333$.