Search Results

Documents authored by Leonhardt, Alexander

Document
DOI: 10.4230/LIPIcs.ESA.2026.18
Efficient Uniform Negative Edge Weights

Authors: Lukas Geis, Daniel Allendorf, Thomas Bläsius, Alexander Leonhardt, Ulrich Meyer, Manuel Penschuck, and Hung Tran

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We consider a maximum entropy edge weight model that allows for negative weights. Given a graph G and possible weights W typically consisting of positive and negative values, the model selects edge weights w ∈ W^m uniformly at random from all weights that do not introduce a negative cycle. We propose an MCMC process and show that it converges to the required distribution. We then engineer an implementation of the process using a dynamic version of Johnson’s algorithm in connection with a bidirectional Dijkstra search as well as an innovative resampling method. We empirically study the performance characteristics of these novel sampling algorithms as well as the output produced by the model.
Cite as

Lukas Geis, Daniel Allendorf, Thomas Bläsius, Alexander Leonhardt, Ulrich Meyer, Manuel Penschuck, and Hung Tran. Efficient Uniform Negative Edge Weights. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{geis_et_al:LIPIcs.ESA.2026.18,
  author =	{Geis, Lukas and Allendorf, Daniel and Bl\"{a}sius, Thomas and Leonhardt, Alexander and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung},
  title =	{{Efficient Uniform Negative Edge Weights}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.18},
  URN =		{urn:nbn:de:0030-drops-271542},
  doi =		{10.4230/LIPIcs.ESA.2026.18},
  annote =	{Keywords: Random Graphs, Shortest Path, Random Edge Weights, Negative Cycles}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.2
Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC

Authors: Deepak Ajwani, Melvin Kallmayer, Alexander Leonhardt, Ulrich Meyer, Ryan O'Connor, and Manuel Penschuck

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
The Fixed Degree Sequence Model (FDSM) asks for a uniform sample from the set of all simple graphs that match a prescribed degree sequence. It is typically implemented using Markov-Chain Monte-Carlo (MCMC) processes, such as Edge Switching or Curveball (and their variants). Yet despite decades of research, rigorous bounds on the mixing times of such processes remain impractical. Consequently, several experimental techniques have been used to derive "empirical lower bounds" on the mixing time. We address the following research questions: (1) Which commonly studied graph-theoretic properties serve as reliable empirical predictors for mixing of FDSM MCMC processes? (2) At what structural scales do these properties operate primarily (i. e., are they predominantly local or global in nature)? (3) How can these properties be characterised and quantified most effectively? To this end, we propose Claim, a novel systematic method to establish empirical lower bounds using learnt classifiers, and compare it to existing methods. Apart from interesting insights into the usage of machine learning for this problem, we also derive robust graph properties with respect to different randomisation algorithms. Although experimental in nature, these results may influence both theorist’s and algorithm engineer’s work on improved bounds and better algorithm respectively.
Cite as

Deepak Ajwani, Melvin Kallmayer, Alexander Leonhardt, Ulrich Meyer, Ryan O'Connor, and Manuel Penschuck. Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ajwani_et_al:LIPIcs.SEA.2026.2,
  author =	{Ajwani, Deepak and Kallmayer, Melvin and Leonhardt, Alexander and Meyer, Ulrich and O'Connor, Ryan and Penschuck, Manuel},
  title =	{{Different Scales of Randomness: Empirical Mixing Times of the Edge Switching and Curveball MCMC}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.2},
  URN =		{urn:nbn:de:0030-drops-260062},
  doi =		{10.4230/LIPIcs.SEA.2026.2},
  annote =	{Keywords: Mixing Time, Graph Randomization, Machine Learning, Edge Switching}
}
Artifact
Software
DOI: 10.4230/artifacts.22475
K-Rho-Shortcutting Heuristics

Authors: Alexander Leonhardt, Ulrich Meyer, and Manuel Penschuck

Abstract
Cite as

Alexander Leonhardt, Ulrich Meyer, Manuel Penschuck. K-Rho-Shortcutting Heuristics (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22475,
   title = {{K-Rho-Shortcutting Heuristics}}, 
   author = {Leonhardt, Alexander and Meyer, Ulrich and Penschuck, Manuel},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:8965d090c1d32ea024b1bb4b111329990a156b37;origin=https://github.com/alleonhardt/k-rho-shortcutting;visit=swh:1:snp:8185b97dfef89ed4f4b0e5ae16a2b7baf76ea267;anchor=swh:1:rev:54e9d8b70fe67eb89761792fc4081482c6f11c9d}{\texttt{swh:1:dir:8965d090c1d32ea024b1bb4b111329990a156b37}} (visited on 2024-11-28)},
   url = {https://github.com/alleonhardt/k-rho-shortcutting},
   doi = {10.4230/artifacts.22475},
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.84
Insights into (k, ρ)-Shortcutting Algorithms

Authors: Alexander Leonhardt, Ulrich Meyer, and Manuel Penschuck

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

Abstract
A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known kρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically.
Cite as

Alexander Leonhardt, Ulrich Meyer, and Manuel Penschuck. Insights into (k, ρ)-Shortcutting Algorithms. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.ESA.2024.84,
  author =	{Leonhardt, Alexander and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{Insights into (k, \rho)-Shortcutting Algorithms}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{84:1--84: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.84},
  URN =		{urn:nbn:de:0030-drops-211554},
  doi =		{10.4230/LIPIcs.ESA.2024.84},
  annote =	{Keywords: Complexity, Approximation, Optimal algorithms, Parallel shortest path}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.37
PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)

Authors: Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track. Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch.
Cite as

Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck. PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM). In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.IPEC.2023.37,
  author =	{Leonhardt, Alexander and Dell, Holger and Haak, Anselm and Kammer, Frank and Meintrup, Johannes and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{37:1--37:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37},
  URN =		{urn:nbn:de:0030-drops-194563},
  doi =		{10.4230/LIPIcs.IPEC.2023.37},
  annote =	{Keywords: PACE 2023 Challenge, Heuristic, Exact, Twin-Width}
}

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