1 Search Results for "Racicot, Jesse"


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

Authors: Hovhannes A. Harutyunyan, Denis Pankratov, and Jesse Racicot

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{harutyunyan_et_al:LIPIcs.MFCS.2021.57,
  author =	{Harutyunyan, Hovhannes A. and Pankratov, Denis and Racicot, Jesse},
  title =	{{Online Domination: The Value of Getting to Know All Your Neighbors}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{57:1--57:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.57},
  URN =		{urn:nbn:de:0030-drops-144979},
  doi =		{10.4230/LIPIcs.MFCS.2021.57},
  annote =	{Keywords: Dominating set, online algorithms, competitive ratio, trees, cactus graphs, bipartite planar graphs, series-parallel graphs, closed neighborhood}
}
  • Refine by Author
  • 1 Harutyunyan, Hovhannes A.
  • 1 Pankratov, Denis
  • 1 Racicot, Jesse

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Dominating set
  • 1 bipartite planar graphs
  • 1 cactus graphs
  • 1 closed neighborhood
  • 1 competitive ratio
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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