License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.47
URN: urn:nbn:de:0030-drops-185810
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18581/
Go to the corresponding LIPIcs Volume Portal

Fotakis, Dimitris ; Gergatsouli, Evangelia ; Pipis, Charilaos ; Stouras, Miltiadis ; Tzamos, Christos

Graph Connectivity with Noisy Queries

pdf-format:
LIPIcs-MFCS-2023-47.pdf (1.0 MB)

Abstract

Graph connectivity is a fundamental combinatorial optimization problem that arises in many practical applications, where usually a spanning subgraph of a network is used for its operation. However, in the real world, links may fail unexpectedly deeming the networks non-operational, while checking whether a link is damaged is costly and possibly erroneous. After an event that has damaged an arbitrary subset of the edges, the network operator must find a spanning tree of the network using non-damaged edges by making as few checks as possible.
Motivated by such questions, we study the problem of finding a spanning tree in a network, when we only have access to noisy queries of the form "Does edge e exist?". We design efficient algorithms, even when edges fail adversarially, for all possible error regimes; 2-sided error (where any answer might be erroneous), false positives (where "no" answers are always correct) and false negatives (where "yes" answers are always correct). In the first two regimes we provide efficient algorithms and give matching lower bounds for general graphs. In the False Negative case we design efficient algorithms for large interesting families of graphs (e.g. bounded treewidth, sparse). Using the previous results, we provide tight algorithms for the practically useful family of planar graphs in all error regimes.

BibTeX - Entry

@InProceedings{fotakis_et_al:LIPIcs.MFCS.2023.47,
  author =	{Fotakis, Dimitris and Gergatsouli, Evangelia and Pipis, Charilaos and Stouras, Miltiadis and Tzamos, Christos},
  title =	{{Graph Connectivity with Noisy Queries}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18581},
  URN =		{urn:nbn:de:0030-drops-185810},
  doi =		{10.4230/LIPIcs.MFCS.2023.47},
  annote =	{Keywords: algorithms under uncertainty, graph connectivity, spanning tree, noisy queries, online algorithms, stochastic optimization}
}

Keywords: algorithms under uncertainty, graph connectivity, spanning tree, noisy queries, online algorithms, stochastic optimization
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI