Online Domination: The Value of Getting to Know All Your Neighbors

Authors Hovhannes A. Harutyunyan, Denis Pankratov, Jesse Racicot



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.57.pdf
  • Filesize: 1.05 MB
  • 21 pages

Document Identifiers

Author Details

Hovhannes A. Harutyunyan
  • Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada
Denis Pankratov
  • Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada
Jesse Racicot
  • Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada

Cite AsGet BibTex

Hovhannes A. Harutyunyan, Denis Pankratov, and Jesse Racicot. Online Domination: The Value of Getting to Know All Your Neighbors. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 57:1-57:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.57

Abstract

We study the dominating set problem in an online setting. An algorithm is required to guarantee competitiveness against an adversary that reveals the input graph one node at a time. When a node is revealed, the algorithm learns about the entire neighborhood of the node (including those nodes that have not yet been revealed). Furthermore, the adversary is required to keep the revealed portion of the graph connected at all times. We present an algorithm that achieves 2-competitiveness on trees. We also present algorithms that achieve 2.5-competitiveness on cactus graphs, (t-1)-competitiveness on K_{1,t}-free graphs, and Θ(√{Δ}) for maximum degree Δ graphs. We show that all of those competitive ratios are tight. Then, we study several more general classes of graphs, such as threshold, bipartite planar, and series-parallel graphs, and show that they do not admit competitive algorithms (i.e., when competitive ratio is independent of the input size). Previously, the dominating set problem was considered in a different input model (often together with the restriction of the input graph being always connected), where a vertex is revealed alongside its restricted neighborhood: those neighbors that are among already revealed vertices. Thus, conceptually, our results quantify the value of knowing the entire neighborhood at the time a vertex is revealed as compared to the restricted neighborhood. For instance, it was known in the restricted neighborhood model that 3-competitiveness is optimal for trees, whereas knowing the neighbors allows us to improve it to 2-competitiveness.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Dominating set
  • online algorithms
  • competitive ratio
  • trees
  • cactus graphs
  • bipartite planar graphs
  • series-parallel graphs
  • closed neighborhood

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. C. Berge. The Theory of Graphs and Its Applications. Methuen, 1962. Google Scholar
  2. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  3. Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, and Kim S. Larsen. Online dominating set. Algorithmica, 81(5):1938-1964, 2019. Google Scholar
  4. Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Dominating set is fixed parameter tractable in claw-free graphs. Theoretical Computer Science, 412(50):6982-7000, 2011. Google Scholar
  5. Bevan Das and Vaduvur Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In 1997 IEEE International Conference on Communications: Towards the Knowledge Millennium, ICC 1997, Montréal, Québec, Canada, June 8-12, 1997, pages 376-380. IEEE, 1997. Google Scholar
  6. Hovhannes Harutyunyan, Denis Pankratov, and Jesse Racicot. Online domination: The value of getting to know all your neighbors, 2021. URL: http://arxiv.org/abs/2105.00299.
  7. Hovhannes A. Harutyunyan. An efficient vertex addition method for broadcast networks. Internet Math., 5(3):211-225, 2008. Google Scholar
  8. Hovhannes A. Harutyunyan and Arthur L. Liestman. Upper bounds on the broadcast function using minimum dominating sets. Discret. Math., 312(20):2992-2996, 2012. Google Scholar
  9. T.W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. Google Scholar
  10. Stephen T. Hedetniemi, Renu C. Laskar, and John Pfaff. A linear algorithm for finding a minimum dominating set in a cactus. Discret. Appl. Math., 13(2-3):287-292, 1986. Google Scholar
  11. M. Henning and A. Yeo. Total Domination in Graphs. Springer-Verlag New York, 2013. Google Scholar
  12. Gow-Hsing King and Wen-Guey Tzeng. On-line algorithms for the dominating set problem. Inf. Process. Lett., 61(1):11-14, 1997. Google Scholar
  13. Koji M. Kobayashi. Improved bounds for online dominating sets of trees. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, volume 92 of LIPIcs, pages 52:1-52:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  14. Dennis Komm. An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2016. Google Scholar
  15. D. König. Theorie der Endlichen und Unendlichen Graphen. Chelsea, New York, 1950. Google Scholar
  16. O. Ore. Theory of Graphs. American Mathematical Society, 1962. Google Scholar
  17. Feng Wang, Ding-Zhu Du, and Xiuzhen Cheng. Connected dominating set, 2016. In Encyclopedia of Algorithms. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail