Search Results

Documents authored by Lakis, Kostas

Document
DOI: 10.4230/LIPIcs.AofA.2026.25
The Dispersion Process Has the Same Phase Transition on Almost Every Graph

Authors: Julius Hallmann, Kostas Lakis, and Tamás Makai

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract
The Dispersion process was introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018), in which a number of particles are initially placed on a given vertex of a graph and update their positions according to the following dynamics. In each round, the particles which are not alone on a vertex (called unhappy) simultaneously move to a uniformly random neighbor. In contrast, the rest of the particles (called happy) stay put. The process terminates once every particle is happy. When the process runs on the complete graph, they showed that there is a phase transition with respect to the running time when the number of particles reaches n/2. Below this threshold the running time is logarithmic, while above the threshold it is exponential. We show that the same behavior holds for the binomial random graph G(n, 1/2) with high probability. The main difference to the complete graph is that the number of happy particles in the neighborhood of a vertex can vary significantly from vertex to vertex, resulting in differing local behaviors. Fortunately the number of such vertices is limited and thus they only have a negligible effect on the running time of the process.
Cite as

Julius Hallmann, Kostas Lakis, and Tamás Makai. The Dispersion Process Has the Same Phase Transition on Almost Every Graph. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 25:1-25:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hallmann_et_al:LIPIcs.AofA.2026.25,
  author =	{Hallmann, Julius and Lakis, Kostas and Makai, Tam\'{a}s},
  title =	{{The Dispersion Process Has the Same Phase Transition on Almost Every Graph}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{25:1--25:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.25},
  URN =		{urn:nbn:de:0030-drops-262960},
  doi =		{10.4230/LIPIcs.AofA.2026.25},
  annote =	{Keywords: Dispersion process, Random Graphs, Drift analysis}
}
Document
DOI: 10.4230/LIPIcs.WG.2026.12
Geometric Routing in Geometric Inhomogeneous Random Graphs

Authors: Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis, and Ulysse Schaller

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract
We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol. While greedy routing in GIRGs is known to explain the algorithmic small-world phenomenon by finding ultra-short paths of length Θ(log log n), it assumes additional knowledge of vertex weights beyond geometry, an assumption that is often restrictive or unavailable. We investigate whether the underlying geometry alone is sufficient for efficient navigation. We prove that for power-law weight exponent τ ∈ (2,3) and geometric decay parameter α > τ-1, geometric routing succeeds with constant probability and finds ultra-short paths of length Θ(log log n), matching the optimal asymptotic guarantees for greedy routing. Our analysis further reveals that, upon success, both protocols follow a similar two-phase trajectory, consisting of a rapid ascent to the heavy vertices, followed by efficient navigation to the target. These results demonstrate that, in the appropriate regime, the network’s geometry alone implicitly guides the path to the target through its high-weight core.
Cite as

Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis, and Ulysse Schaller. Geometric Routing in Geometric Inhomogeneous Random Graphs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.WG.2026.12,
  author =	{Chiu, Yu-Cheng and Kaufmann, Marc and Lakis, Kostas and Schaller, Ulysse},
  title =	{{Geometric Routing in Geometric Inhomogeneous Random Graphs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan 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.WG.2026.12},
  URN =		{urn:nbn:de:0030-drops-261780},
  doi =		{10.4230/LIPIcs.WG.2026.12},
  annote =	{Keywords: geometric inhomogeneous random graphs (GIRGs), hyperbolic random graphs (HRGs), greedy routing, geometric routing, navigability, small-world phenomenon, decentralized algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.11
The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs

Authors: Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is asymptotically almost surely Θ(log n). This has strong implications for the runtime of many distributed protocols on those graphs, which often have runtimes bounded as a function of the diameter. The GIRG model exhibits many properties empirically found in real-world networks, and the runtime of various practical algorithms has empirically been found to scale in the same way for GIRG and for real-world networks, in particular related to computing distances, diameter, clustering, cliques and chromatic numbers. Thus the GIRG model is a promising candidate for deriving insight about the performance of algorithms in real-world instances. The diameter was previously only known in the one-dimensional case, and the proof relied very heavily on dimension one. Our proof employs a similar Peierls-type argument alongside a novel renormalization scheme. Moreover, instead of using topological arguments (which become complicated in high dimensions) in establishing the connectivity of certain boundaries, we employ some comparatively recent and clearer graph-theoretic machinery. The lower bound is proven via a simple ad-hoc construction.
Cite as

Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi. The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benjert_et_al:LIPIcs.STACS.2026.11,
  author =	{Benjert, Zylan and Lakis, Kostas and Lengler, Johannes and Ravi, Raghu Raman},
  title =	{{The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.11},
  URN =		{urn:nbn:de:0030-drops-255009},
  doi =		{10.4230/LIPIcs.STACS.2026.11},
  annote =	{Keywords: GIRG, Diameter, Distributed Algorithms, Complex Networks}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.74
Improved Bounds for Graph Distances in Scale Free Percolation and Related Models

Authors: Kostas Lakis, Johannes Lengler, Kalina Petrova, and Leon Schiller

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HRG. Despite the wide success of the models, the parameter regime in which graph distances are polylogarithmic is poorly understood. We provide new and improved lower bounds. In a certain portion of the parameter regime, those match the known upper bounds. Compared to the best previous lower bounds by Hao and Heydenreich [Hao and Heydenreich, 2023], our result has several advantages: it gives matching bounds for a larger range of parameters, thus settling the question for a larger portion of the parameter space. It strictly improves the lower bounds of [Hao and Heydenreich, 2023] for all parameters settings in which those bounds were not tight. It gives tail bounds on the probability of having short paths, which imply shape theorems for the k-neighbourhood of a vertex whenever our lower bounds are tight, and tight bounds for the size of this k-neighbourhood. And last but not least, our proof is much simpler and not much longer than two pages, and we demonstrate that it generalizes well by showing that the same technique also works for first passage percolation.
Cite as

Kostas Lakis, Johannes Lengler, Kalina Petrova, and Leon Schiller. Improved Bounds for Graph Distances in Scale Free Percolation and Related Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 74:1-74:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lakis_et_al:LIPIcs.APPROX/RANDOM.2024.74,
  author =	{Lakis, Kostas and Lengler, Johannes and Petrova, Kalina and Schiller, Leon},
  title =	{{Improved Bounds for Graph Distances in Scale Free Percolation and Related Models}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{74:1--74:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.74},
  URN =		{urn:nbn:de:0030-drops-210676},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.74},
  annote =	{Keywords: Mathematics, Probability Theory, Combinatorics, Random Graphs, Random Metric Spaces}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.12
Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else

Authors: Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a sequence of initially unknown requests arrive over time at points (locations) of a metric space. The goal is, starting from a particular point of the metric space (the origin), to serve all these requests while minimizing the total time spent. The server moves with unit speed or is "waiting" (zero speed) at some location. We consider two variants: in the open variant, the goal is achieved when the last request is served. In the closed one, the server additionally has to return to the origin. We adopt a prediction model, introduced for OLTSP on the line [Gouleakis et al., 2023], in which the predictions correspond to the locations of the requests and extend it to more general metric spaces. We first propose an oracle-based algorithmic framework, inspired by previous work [Bampis et al., 2023]. This framework allows us to design online algorithms for general metric spaces that provide competitive ratio guarantees which, given perfect predictions, beat the best possible classical guarantee (consistency). Moreover, they degrade gracefully along with the increase in error (smoothness), but always within a constant factor of the best known competitive ratio in the classical case (robustness). Having reduced the problem to designing suitable efficient oracles, we describe how to achieve this for general metric spaces as well as specific metric spaces (rings, trees and flowers), the resulting algorithms being tractable in the latter case. The consistency guarantees of our algorithms are tight in almost all cases, and their smoothness guarantees only suffer a linear dependency on the error, which we show is necessary. Finally, we provide robustness guarantees improving previous results.
Cite as

Evripidis Bampis, Bruno Escoffier, Themis Gouleakis, Niklas Hahn, Kostas Lakis, Golnoosh Shahkarami, and Michalis Xefteris. Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ESA.2023.12,
  author =	{Bampis, Evripidis and Escoffier, Bruno and Gouleakis, Themis and Hahn, Niklas and Lakis, Kostas and Shahkarami, Golnoosh and Xefteris, Michalis},
  title =	{{Learning-Augmented Online TSP on Rings, Trees, Flowers and (Almost) Everywhere Else}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.12},
  URN =		{urn:nbn:de:0030-drops-186659},
  doi =		{10.4230/LIPIcs.ESA.2023.12},
  annote =	{Keywords: TSP, Online algorithms, Learning-augmented algorithms, Algorithms with predictions, Competitive analysis}
}
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