Alexander Leonhardt

Lukas Geis, Daniel Allendorf, Thomas Bläsius et al.

We consider a maximum entropy edge weight model that allows for negative weights. Given a graph $G$ and possible weights $\mathcal{W}$ typically consisting of positive and negative values, the model selects edge weights $w \in \mathcal{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.

Tatiana Rocha Avila, Julian Christoph Brinkmann, Alexander Leonhardt et al.

We consider the Minimum-$(k,ρ)$-$\mathrm{Shortcut}$ problem ($\min(k,ρ)\text{-}\mathrm{Shortcut}$), where the goal is to find the smallest set of shortcut edges such that every vertex in a given graph can reach its $ρ$ closest vertices using paths of at most $k$ edges. This is a fundamental graph optimization problem used to accelerate parallel shortest path algorithms. It is well-known that the problem is trivially solvable for the cases $k=1$ and $k\geqρ$. While recent work by Leonhardt, Meyer, and Penschuck (ESA 2024) showed that in undirected graphs $\min(k,ρ)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq 3$ if $ρ=Θ(n^ε)$, the boundary where the problem transitions from polynomial-time solvable to NP-hard remained open. In this paper, we narrow this gap significantly. We present a simpler and more direct reduction from the Hitting Set problem which establishes that $\min(k,ρ)\text{-}\mathrm{Shortcut}$ is NP-hard for $k\geq2$ and $ρ\geq k+2$ in both directed and undirected graphs. Complementing this, we use the symmetry of the undirected case to show that $ρ=k+1$ is solvable in polynomial time, a regime where the directed version remains a candidate for NP-hardness. Therefore, we obtain an almost complete characterization of the complexity of $\min(k,ρ)\text{-}\mathrm{Shortcut}$, with the sole remaining open case being $ρ= k+1$ in the directed setting.