Kobayashi, Koji M.
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 NPhard 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 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 Zurich, 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.
BibTeX  Entry
@InProceedings{kobayashi:LIPIcs:2017:8236,
author = {Koji M. Kobayashi},
title = {{Improved Bounds for Online Dominating Sets of Trees}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {52:152:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8236},
URN = {urn:nbn:de:0030drops82364},
doi = {10.4230/LIPIcs.ISAAC.2017.52},
annote = {Keywords: online algorithm, dominating set, competitive analysis, tree graph, randomized algorithm}
}
07.12.2017
Keywords: 

online algorithm, dominating set, competitive analysis, tree graph, randomized algorithm 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 