25 Search Results for "Leucci, Stefano"

Document
DOI: 10.4230/LIPIcs.ESA.2024.11
How to Reduce Temporal Cliques to Find Sparse Spanners

Authors: Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with 𝒪(nlog n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them. This allows us to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and using this, we provide a simpler and more intuitive proof of the 𝒪(nlog n) bound by giving an efficient algorithm for finding linearithmic spanners. Moreover, we use our novel and efficiently computable approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel algorithmic techniques for establishing the existence of linear temporal spanners in these graph classes as well.
Cite as

Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells. How to Reduce Temporal Cliques to Find Sparse Spanners. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.ESA.2024.11,
  author =	{Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin},
  title =	{{How to Reduce Temporal Cliques to Find Sparse Spanners}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.11},
  URN =		{urn:nbn:de:0030-drops-210822},
  doi =		{10.4230/LIPIcs.ESA.2024.11},
  annote =	{Keywords: Temporal Graphs, temporal Clique, temporal Spanner, Reachability, Graph Connectivity, Graph Sparsification}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.25
Graph Spanners for Group Steiner Distances

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A spanner is a sparse subgraph of a given graph G which preserves distances, measured w.r.t. some distance metric, up to a multiplicative stretch factor. This paper addresses the problem of constructing graph spanners w.r.t. the group Steiner metric, which generalizes the recently introduced beer distance metric. In such a metric we are given a collection of groups of required vertices, and we measure the distance between two vertices as the length of the shortest path between them that traverses at least one required vertex from each group. We discuss the relation between group Steiner spanners and classic spanners and we show that they exhibit strong ties with sourcewise spanners w.r.t. the shortest path metric. Nevertheless, group Steiner spanners capture several interesting scenarios that are not encompassed by existing spanners. This happens, e.g., for the singleton case, in which each group consists of a single required vertex, thus modeling the setting in which routes need to traverse certain points of interests (in any order). We provide several constructions of group Steiner spanners for both the all-pairs and single-source case, which exhibit various size-stretch trade-offs. Notably, we provide spanners with almost-optimal trade-offs for the singleton case. Moreover, some of our spanners also yield novel trade-offs for classical sourcewise spanners. Finally, we also investigate the query times that can be achieved when our spanners are turned into group Steiner distance oracles with the same size, stretch, and building time.
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, and Alessandro Straziota. Graph Spanners for Group Steiner Distances. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2024.25,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Straziota, Alessandro},
  title =	{{Graph Spanners for Group Steiner Distances}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.25},
  URN =		{urn:nbn:de:0030-drops-210968},
  doi =		{10.4230/LIPIcs.ESA.2024.25},
  annote =	{Keywords: Network sparsification, Graph spanners, Group Steiner tree, Distance oracles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.36
Bicriteria Approximation for Minimum Dilation Graph Augmentation

Authors: Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget k, which k edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in k. Our main result is a (2 √[r]{2} k^{1/r},2r)-bicriteria approximation that runs in O(n³ log n) time, for all r ≥ 1. In other words, if t^* is the minimum dilation after adding any k edges to a graph, then our algorithm adds O(k^{1+1/r}) edges to the graph to obtain a dilation of 2rt^*. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture.
Cite as

Kevin Buchin, Maike Buchin, Joachim Gudmundsson, and Sampson Wong. Bicriteria Approximation for Minimum Dilation Graph Augmentation. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2024.36,
  author =	{Buchin, Kevin and Buchin, Maike and Gudmundsson, Joachim and Wong, Sampson},
  title =	{{Bicriteria Approximation for Minimum Dilation Graph Augmentation}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.36},
  URN =		{urn:nbn:de:0030-drops-211079},
  doi =		{10.4230/LIPIcs.ESA.2024.36},
  annote =	{Keywords: Greedy spanner, Graph augmentation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.65
A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles

Authors: Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
An α-approximate vertex fault-tolerant distance sensitivity oracle (α-VSDO) for a weighted input graph G = (V, E, w) and a source vertex s ∈ V is the data structure answering an α-approximate distance from s to t in G-x for any given query (x, t) ∈ V × V. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new nearly linear-time algorithm of constructing a (1 + ε)-VSDO for any directed input graph with polynomially bounded integer edge weights. More precisely, the presented oracle attains Õ(m log (nW)/ ε + n log² (nW)/ε²) construction time, Õ(n log (nW) / ε) size, and Õ(1/ε) query time, where n is the number of vertices, m is the number of edges, and W is the maximum edge weight. These bounds are all optimal up to polylogarithmic factors. To the best of our knowledge, this is the first non-trivial algorithm for SSRP/VSDO beating Õ(mn) computation time for directed graphs with general edge weight functions, and also the first nearly linear-time construction breaking approximation factor 3. Such a construction has been unknown even for undirected and unweighted graphs. In addition, our result implies that the known conditional lower bounds for the exact SSRP computation does not apply to the case of approximation.
Cite as

Kaito Harada, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harada_et_al:LIPIcs.ESA.2024.65,
  author =	{Harada, Kaito and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
  title =	{{A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{65:1--65:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.65},
  URN =		{urn:nbn:de:0030-drops-211367},
  doi =		{10.4230/LIPIcs.ESA.2024.65},
  annote =	{Keywords: data structure, distance sensitivity oracle, replacement path problem, graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.4
Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard

Authors: Davide Bilò, Luca Di Donato, Luciano Gualà, and Stefano Leucci

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
We study the Solo-Chess problem which has been introduced in [Aravind et al., FUN 2022]. This is a single-player variant of chess in which the player must clear all but one piece from the board via a sequence captures while ensuring that the number of captures performed by each piece does not exceed the piece’s budget. The time complexity of finding a winning sequence of captures has already been pinpointed for several combination of piece types and initial budgets. We contribute to a better understanding of the computational landscape of Solo-Chess by closing two problems left open in [Aravind et al., FUN 2022]. Namely, we show that Solo-Chess is hard even when all pieces are restricted to be only rooks with budget exactly 2, or only knights with budget exactly 11.
Cite as

Davide Bilò, Luca Di Donato, Luciano Gualà, and Stefano Leucci. Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2024.4,
  author =	{Bil\`{o}, Davide and Di Donato, Luca and Gual\`{a}, Luciano and Leucci, Stefano},
  title =	{{Uniform-Budget Solo Chess with Only Rooks or Only Knights Is Hard}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.4},
  URN =		{urn:nbn:de:0030-drops-199121},
  doi =		{10.4230/LIPIcs.FUN.2024.4},
  annote =	{Keywords: solo chess, puzzle games, board games, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.5
Swapping Mixed-Up Beers to Keep Them Cool

Authors: Davide Bilò, Maurizio Fiusco, Luciano Gualà, and Stefano Leucci

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
There was a mix-up in Escher’s bar and n customers sitting at the same table have each received a beer ordered by somebody else in the party. The drinks can be rearranged by swapping them in pairs, but the eccentric table shape only allows drinks to be exchanged between people sitting on opposite sides of the table. We study the problem of finding the minimum number of swaps needed so that each customer receives its desired beer before it gets warm. Formally, we consider the Colored Token Swapping problem on complete bipartite graphs. This problem is known to be solvable in polynomial time when all ordered drinks are different [Yamanaka et al., FUN 2014], but no results are known for the more general case in which multiple people in the party can order the same beer. We prove that Colored Token Swapping on complete bipartite graphs is NP-hard and that it is fixed-parameter tractable when parameterized by the number of distinct types of beer served by the bar.
Cite as

Davide Bilò, Maurizio Fiusco, Luciano Gualà, and Stefano Leucci. Swapping Mixed-Up Beers to Keep Them Cool. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2024.5,
  author =	{Bil\`{o}, Davide and Fiusco, Maurizio and Gual\`{a}, Luciano and Leucci, Stefano},
  title =	{{Swapping Mixed-Up Beers to Keep Them Cool}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.5},
  URN =		{urn:nbn:de:0030-drops-199132},
  doi =		{10.4230/LIPIcs.FUN.2024.5},
  annote =	{Keywords: Colored Token Swapping, Complete Bipartite Graphs, Labeled Token Swapping, FPT Algorithms, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.37
Approximate Selection with Unreliable Comparisons in Optimal Expected Time

Authors: Shengyu Huang, Chih-Hung Liu, and Daniel Rutschmann

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log 1/Q), Θ(n log k/Q) and Θ(n log n/Q) comparisons, respectively, to achieve success probability 1-Q [Uriel Feige et al., 1994]. Considering the increasing complexity of modern computing, it is of great interest to develop approximation algorithms that enable a trade-off between the solution quality and the number of comparisons. In particular, approximation algorithms would even be able to attain a sublinear number of comparisons. Very recently, Leucci and Liu [Stefano Leucci and Chih-Hung Liu, 2022] proved that the approximate minimum selection problem, which covers the case that k ≤ nε, requires expected Θ(ε^{-1} log 1/Q) comparisons, but the general case, i.e., for nε < k ≤ n/2, is still open. We develop a randomized algorithm that performs expected O(k/n ε^{-2} log 1/Q) comparisons to achieve success probability at least 1-Q. For k = n ε, the number of comparisons is O(ε^{-1} log 1/Q), matching Leucci and Liu’s result [Stefano Leucci and Chih-Hung Liu, 2022], whereas for k = n/2 (i.e., approximating the median), the number of comparisons is O(ε^{-2} log 1/Q). We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(min{n, k/n ε^{-2} log 1/Q}) comparisons. As long as n is large enough, i.e., when n = Ω(k/n ε^{-2} log 1/Q), our lower bound demonstrates the optimality of our algorithm, which covers the possible range of attaining a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε^{-2}) comparisons, matching the best possible approximation algorithm in the absence of computation faults. In contrast, for the exact selection problem, the expected number of comparisons is Θ(n log k) with faults versus Θ(n) without faults. Our results also indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k = n/2, Q = 1/n and ε = n^{-α} for α ∈ (0, 1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^{2α}).
Cite as

Shengyu Huang, Chih-Hung Liu, and Daniel Rutschmann. Approximate Selection with Unreliable Comparisons in Optimal Expected Time. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2023.37,
  author =	{Huang, Shengyu and Liu, Chih-Hung and Rutschmann, Daniel},
  title =	{{Approximate Selection with Unreliable Comparisons in Optimal Expected Time}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.37},
  URN =		{urn:nbn:de:0030-drops-176898},
  doi =		{10.4230/LIPIcs.STACS.2023.37},
  annote =	{Keywords: Approximate Selection, Unreliable Comparisons, Independent Faults}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.19
Sparse Temporal Spanners with Low Stretch

Authors: Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, and Mirko Rossi

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A temporal graph is an undirected graph G = (V,E) along with a function λ : E → ℕ^+ that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., the number of edges) of a temporal path from u to v. A temporal α-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V, up to a multiplicative stretch factor of α. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k-1)-spanner with Õ(kn^{1+1/k}) edges, where k > 1 is an integer parameter of choice. Choosing k = ⌊log n⌋, we obtain a temporal O(log n)-spanner with Õ(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then turn our attention to general temporal graphs. Since Ω(n²) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that Õ(n/log(1+ε)) edges suffice to obtain a stretch of (1+ε), for any small ε > 0. This result is essentially tight in the following sense: there are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use Ω(n²) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of Õ(n² / β) on the size of any temporal β-additive spanner, which we show to be tight up to polylogarithmic factors. Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner.
Cite as

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, and Mirko Rossi. Sparse Temporal Spanners with Low Stretch. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ESA.2022.19,
  author =	{Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Rossi, Mirko},
  title =	{{Sparse Temporal Spanners with Low Stretch}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.19},
  URN =		{urn:nbn:de:0030-drops-169575},
  doi =		{10.4230/LIPIcs.ESA.2022.19},
  annote =	{Keywords: temporal spanners, temporal graphs, graph sparsification, approximate distances}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.12
Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers

Authors: Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Let G be a directed graph with n vertices, m edges, and non-negative edge costs. Given G, a fixed source vertex s, and a positive integer p, we consider the problem of computing, for each vertex t≠ s, p edge-disjoint paths of minimum total cost from s to t in G. Suurballe and Tarjan [Networks, 1984] solved the above problem for p = 2 by designing a O(m+nlog n) time algorithm which also computes a sparse single-source 2-multipath preserver, i.e., a subgraph containing 2 edge-disjoint paths of minimum total cost from s to every other vertex of G. The case p ≥ 3 was left as an open problem. We study the general problem (p ≥ 2) and prove that any graph admits a sparse single-source p-multipath preserver with p(n-1) edges. This size is optimal since the in-degree of each non-root vertex v must be at least p. Moreover, we design an algorithm that requires O(pn² (p + log n)) time to compute both p edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source p-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves n-1 single-pair instances using the well-known successive shortest paths algorithm by a factor of Θ(m/(np)) and is asymptotically near optimal if p = O(1) and m = Θ(n²). Our results extend naturally to the case of p vertex-disjoint paths.
Cite as

Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti, and Mirko Rossi. Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.STACS.2022.12,
  author =	{Bil\`{o}, Davide and D'Angelo, Gianlorenzo and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Rossi, Mirko},
  title =	{{Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.12},
  URN =		{urn:nbn:de:0030-drops-158221},
  doi =		{10.4230/LIPIcs.STACS.2022.12},
  annote =	{Keywords: multipath spanners, graph sparsification, edge-disjoint paths, min-cost flow}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.66
Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees

Authors: Luciano Gualà, Stefano Leucci, and Isabella Ziccardi

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We study the problem of designing a resilient data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC'04] in which up to δ memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports resilient (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in O(δ) worst-case time per operation.
Cite as

Luciano Gualà, Stefano Leucci, and Isabella Ziccardi. Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guala_et_al:LIPIcs.ISAAC.2021.66,
  author =	{Gual\`{a}, Luciano and Leucci, Stefano and Ziccardi, Isabella},
  title =	{{Resilient Level Ancestor, Bottleneck, and Lowest Common Ancestor Queries in Dynamic Trees}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{66:1--66:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.66},
  URN =		{urn:nbn:de:0030-drops-154998},
  doi =		{10.4230/LIPIcs.ISAAC.2021.66},
  annote =	{Keywords: level ancestor queries, lowest common ancestor queries, bottleneck vertex queries, resilient data structures, faulty-RAM model, dynamic trees}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.5
Cutting Bamboo down to Size

Authors: Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O(log n) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to (3+√5)/2 < 2.62 for x = 1+1/√5. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).
Cite as

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca. Cutting Bamboo down to Size. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2021.5,
  author =	{Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Scornavacca, Giacomo},
  title =	{{Cutting Bamboo down to Size}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.5},
  URN =		{urn:nbn:de:0030-drops-127663},
  doi =		{10.4230/LIPIcs.FUN.2021.5},
  annote =	{Keywords: bamboo garden trimming, trimming oracles, approximation algorithms, pinwheel scheduling}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.64
Dual-Mode Greedy Algorithms Can Save Energy

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti. Dual-Mode Greedy Algorithms Can Save Energy. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ISAAC.2019.64,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo and Proietti, Guido},
  title =	{{Dual-Mode Greedy Algorithms Can Save Energy}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.64},
  URN =		{urn:nbn:de:0030-drops-115604},
  doi =		{10.4230/LIPIcs.ISAAC.2019.64},
  annote =	{Keywords: matroids, p-extendible systems, greedy algorithm, approximation algorithms, high-low energy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.49
Optimal Sorting with Persistent Comparison Errors

Authors: Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated (Braverman and Mossel, SODA'08). Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Omega(log n) and Omega(n), respectively, regardless of its running time. In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds. In order to achieve this optimality result, we solve two sub-problems in the persistent error comparisons model, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted.
Cite as

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Sorting with Persistent Comparison Errors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{geissmann_et_al:LIPIcs.ESA.2019.49,
  author =	{Geissmann, Barbara and Leucci, Stefano and Liu, Chih-Hung and Penna, Paolo},
  title =	{{Optimal Sorting with Persistent Comparison Errors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.49},
  URN =		{urn:nbn:de:0030-drops-111706},
  doi =		{10.4230/LIPIcs.ESA.2019.49},
  annote =	{Keywords: approximate sorting, comparison errors, persistent errors}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.70
Resilient Dictionaries for Randomly Unreliable Memory

Authors: Stefano Leucci, Chih-Hung Liu, and Simon Meierhans

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study the problem of designing a dictionary data structure that is resilient to memory corruptions. Our error model is a variation of the faulty RAM model in which, except for constant amount of definitely reliable memory, each memory word is randomly unreliable with a probability p < 1/2, and the locations of the unreliable words are unknown to the algorithm. An adversary observes the whole memory and can, at any time, arbitrarily corrupt (i.e., modify) the contents of one or more unreliable words. Our dictionary has capacity n, stores N<n keys in the optimal O(N) amount of space, supports insertions and deletions in O(log n) amortized time, and allows to search for a key in O(log n) worst-case time. With a global probability of at least 1-1/n, all possible search operations are guaranteed to return the correct answer w.r.t. the set of uncorrupted keys. The closest related results are the ones of Finocchi et al. [Irene Finocchi et al., 2009] and Brodal et al. [Brodal et al., 2007] on the faulty RAM model, in which all but O(1) memory is unreliable. There, if an upper bound delta on the number of corruptions is known in advance, all dictionary operations can be implemented in Theta(log n + delta) amortized time, thus trading resiliency for speed as soon as delta = omega(log n). Our construction does not need to know the value of delta in advance and remains fast and effective even when up to a constant fraction of the available memory is corrupted. Our techniques can be immediately extended to implement other data types (e.g., associative containers and priority queues), which can then be used as a building block in the design of other resilient algorithms. For example, we are able to solve the resilient sorting problem in our model using O(n log n) time.
Cite as

Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient Dictionaries for Randomly Unreliable Memory. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leucci_et_al:LIPIcs.ESA.2019.70,
  author =	{Leucci, Stefano and Liu, Chih-Hung and Meierhans, Simon},
  title =	{{Resilient Dictionaries for Randomly Unreliable Memory}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.70},
  URN =		{urn:nbn:de:0030-drops-111911},
  doi =		{10.4230/LIPIcs.ESA.2019.70},
  annote =	{Keywords: resilient dictionary, unreliable memory, faulty RAM}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.4
Tracks from hell - when finding a proof may be easier than checking it

Authors: Matteo Almanza, Stefano Leucci, and Alessandro Panconesi

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.
Cite as

Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Tracks from hell - when finding a proof may be easier than checking it. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{almanza_et_al:LIPIcs.FUN.2018.4,
  author =	{Almanza, Matteo and Leucci, Stefano and Panconesi, Alessandro},
  title =	{{Tracks from hell - when finding a proof may be easier than checking it}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.4},
  URN =		{urn:nbn:de:0030-drops-87954},
  doi =		{10.4230/LIPIcs.FUN.2018.4},
  annote =	{Keywords: puzzle games, solitaire games, Trainyard, verification}
}
  • Refine by Author
  • 21 Leucci, Stefano
  • 13 Gualà, Luciano
  • 11 Bilò, Davide
  • 8 Proietti, Guido
  • 6 Liu, Chih-Hung
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Problems, reductions and completeness
  • 3 Theory of computation → Data structures design and analysis
  • 3 Theory of computation → Sparsification and spanners
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 Complexity of Games
  • 2 Trainyard
  • 2 approximation algorithms
  • 2 distance sensitivity oracle
  • 2 fault-tolerant shortest-path tree
  • Show More...

  • Refine by Type
  • 25 document

  • Refine by Publication Year
  • 6 2024
  • 5 2018
  • 4 2016
  • 3 2019
  • 2 2017
  • Show More...

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact