DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2024.20

Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength

Authors: Paul Bastide and Carla Groenland

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract

In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the shortest path distance between u and v in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an n-vertex connected graph G parameterized by maximum degree Δ and treelength k in O_{k,Δ}(n log² n) queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength.

Cite as

Paul Bastide and Carla Groenland. Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 20:1-20:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bastide_et_al:LIPIcs.IPEC.2024.20,
  author =	{Bastide, Paul and Groenland, Carla},
  title =	{{Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{20:1--20:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.20},
  URN =		{urn:nbn:de:0030-drops-222465},
  doi =		{10.4230/LIPIcs.IPEC.2024.20},
  annote =	{Keywords: Distance Reconstruction, Randomized Algorithm, Treelength}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2021.47

Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models

Authors: Paul Bastide and Pierre Fraigniaud

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

Given any task Π, Brandt’s speedup theorem (PODC 2019) provides a mechanical way to design another task Π' on the same input-set as Π such that, for any t ≥ 1, Π is solvable in t rounds in the LOCAL model if and only if Π' is solvable in t-1 rounds in the LOCAL model. We dissect the construction in Brandt’s speedup theorem for expressing it in the broader framework of all round-based models supporting full information protocols, which includes models as different as asynchronous wait-free shared-memory computing with iterated immediate snapshots, and synchronous failure-free network computing.

Cite as

Paul Bastide and Pierre Fraigniaud. Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 47:1-47:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bastide_et_al:LIPIcs.DISC.2021.47,
  author =	{Bastide, Paul and Fraigniaud, Pierre},
  title =	{{Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{47:1--47:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.47},
  URN =		{urn:nbn:de:0030-drops-148492},
  doi =		{10.4230/LIPIcs.DISC.2021.47},
  annote =	{Keywords: Local Checkability, Distributed Complexity and Computability}
}

Search Results

Documents authored by Bastide, Paul

Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength

Abstract

Cite as

Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models

Abstract

Cite as

Thanks for your feedback!

Could not send message