4 Search Results for "Gawendowicz, Hans"

Document
DOI: 10.4230/LIPIcs.SAND.2025.6
Dismountability in Temporal Cliques Revisited

Authors: Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges chronologically (temporal paths). Unlike static graphs, temporal graphs do not always admit small subsets of edges that preserve connectivity (temporal spanners) - there exist temporal graphs with Θ(n²) edges, all of which are critical. In the case of temporal cliques (the underlying graph is complete), spanners of size O(nlog n) are guaranteed. The original proof of this result by Casteigts et al. [ICALP 2019] combines a number of techniques, one of which is called dismountability. In a recent work, Angrick et al. [ESA 2024] simplified the proof and showed, among other things, that a one-sided version of dismountability can replace elegantly the second part of the proof. In this paper, we revisit methodically the dismountability principle. We start by characterizing the structure that a temporal clique must have if it is non 1-hop dismountable, then neither 1-hop nor 2-hop (i.e. non {1,2}-hop) dismountable, and finally non {1,2,3}-hop dismountable. It turns out that if a clique is k-hop dismountable for any other k, then it must also be {1,2,3}-hop dismountable, thus no additional structure can be obtained beyond this point. Interestingly, excluding 1-hop and 2-hop dismountability is already sufficient for reducing the spanner problem from cliques to extremally matched bicliques, where the O(nlog n) result is subsequently obtained. Put together with the strategy of Angrick et al., this entire result can now be recovered using only dismountability. An interesting by-product of our analysis is that any minimal counter-example to the existence of 4n spanners must satisfy the properties of non {1,2,3}-hop dismountable cliques. In the second part, we discuss further connections between dismountability and another technique called pivotability. In particular, we show that if a temporal clique is recursively k-hop dismountable, then it is also pivotable (and thus admits a 2n spanner, whatever k). We also study a family of labelings called full-range that forces both dismountability and pivotability. The latter gives some evidence that large lifetimes could be exploited more generally for the construction of spanners.
Cite as

Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini. Dismountability in Temporal Cliques Revisited. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carnevale_et_al:LIPIcs.SAND.2025.6,
  author =	{Carnevale, Daniele and Casteigts, Arnaud and Corsini, Timoth\'{e}e},
  title =	{{Dismountability in Temporal Cliques Revisited}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.6},
  URN =		{urn:nbn:de:0030-drops-230591},
  doi =		{10.4230/LIPIcs.SAND.2025.6},
  annote =	{Keywords: Dynamic networks, Temporal graphs, Reachability, Dismountability, Pivotability, Temporal spanners, Full-range graphs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.3
Temporal Connectivity Augmentation

Authors: Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Connectivity in temporal graphs relies on the notion of temporal paths, in which edges follow a chronological order (either strict or non-strict). In this work, we investigate the question of how to make a temporal graph connected. More precisely, we tackle the problem of finding, among a set of proposed temporal edges, the smallest subset such that its addition makes the graph temporally connected (TCA). We study the complexity of this problem and variants, under restricted lifespan of the graph, i.e. the maximum time step in the graph. Our main result on TCA is that for any fixed lifespan at least 2, it is NP-complete in both the strict and non-strict setting. We additionally provide a set of restrictions in the non-strict setting which makes the problem solvable in polynomial time and design an algorithm achieving this complexity. Interestingly, we prove that the source variant (making a given vertex a source in the augmented graph) is as difficult as TCA. On the opposite, we prove that the version where a list of connectivity demands has to be satisfied is solvable in polynomial time, when the size of the list is fixed. Finally, we highlight a variant of the previous case for which even with two pairs the problem is already NP-hard.
Cite as

Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier. Temporal Connectivity Augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2025.3,
  author =	{Bellitto, Thomas and Popper, Jules Bouton and Escoffier, Bruno},
  title =	{{Temporal Connectivity Augmentation}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.3},
  URN =		{urn:nbn:de:0030-drops-230565},
  doi =		{10.4230/LIPIcs.SAND.2025.3},
  annote =	{Keywords: Temporal graph, temporal connectivity}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.62
Social Distancing Network Creation

Authors: Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
During a pandemic people have to find a trade-off between meeting others and staying safely at home. While meeting others is pleasant, it also increases the risk of infection. We consider this dilemma by introducing a game-theoretic network creation model in which selfish agents can form bilateral connections. They benefit from network neighbors, but at the same time, they want to maximize their distance to all other agents. This models the inherent conflict that social distancing rules impose on the behavior of selfish agents in a social network. Besides addressing this familiar issue, our model can be seen as the inverse to the well-studied Network Creation Game by Fabrikant et al. [PODC 2003] where agents aim at being as central as possible in the created network. Thus, our work is in-line with studies that compare minimization problems with their maximization versions. We look at two variants of network creation governed by social distancing. In the first variant, there are no restrictions on the connections being formed. We characterize optimal and equilibrium networks, and we derive asymptotically tight bounds on the Price of Anarchy and Price of Stability. The second variant is the model’s generalization that allows restrictions on the connections that can be formed. As our main result, we prove that Swap-Maximal Routing-Cost Spanning Trees, an efficiently computable weaker variant of Maximum Routing-Cost Spanning Trees, actually resemble equilibria for a significant range of the parameter space. Moreover, we give almost tight bounds on the Price of Anarchy and Price of Stability. These results imply that, compared the well-studied inverse models, under social distancing the agents' selfish behavior has a significantly stronger impact on the quality of the equilibria, i.e., allowing socially much worse stable states.
Cite as

Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko. Social Distancing Network Creation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.ICALP.2022.62,
  author =	{Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna},
  title =	{{Social Distancing Network Creation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{62:1--62:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.62},
  URN =		{urn:nbn:de:0030-drops-164038},
  doi =		{10.4230/LIPIcs.ICALP.2022.62},
  annote =	{Keywords: Algorithmic Game Theory, Equilibrium Existence, Price of Anarchy, Network Creation Game, Social Distancing, Maximization vs. Minimization Problems}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2022

  • Refine by Author
  • 2 Friedrich, Tobias
  • 2 Gawendowicz, Hans
  • 2 Lenzner, Pascal
  • 1 Angrick, Sebastian
  • 1 Bals, Ben
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Paths and connectivity problems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 Reachability
  • 1 Algorithmic Game Theory
  • 1 Dismountability
  • 1 Dynamic networks
  • 1 Equilibrium Existence
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact