28.04.2023

# Three Papers accepted at ICALP

For the competitive International Colloquium on Automata, Languages and Programming (ICALP) with an acceptance rate of 30% three papers of our group were accepted. The conference will take place on 10-14 July in Paderborn, Germany. The first paper *Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs *is based on the master thesis of Leon Schiller and investigated the influence of the dimension of the underlying metric space on Geometric Inhomogeneous Random Graphs (GIRGs). The authors prove that the model loses its geometry (i.e. converges in total variation distance to its non-geometric counterpart) in the infinite dimensional limit, and further prove tight bounds on the number of cliques and the clique number (size of the largest clique) that explicitly depend on the dimension. They find that, if the dimension scales superlogarithmically, the model essentially behaves like its non-geometric counterpart w.r.t. the clique structure.

The paper *Fault-Tolerant ST-Diameter Oracles* is a cooperation of a large group with authors from several universities and introduces structures that estimate the diameter of a graph under the existence of edge failures. To create these structures they use reductions from existing Fault-Tolerant Distance Sensitivity Oracles which estimate distances between pairs of nodes in a graph with edge failures. Additionally they give a lower bound on the space requirement of such diameter oracles.

Lastly, in the paper *Approximating Long Cycle Above Dirac’s Guarantee*, the authors show that any approximation algorithm for Longest Cycle could be effectively applied on top of Dirac's existential guarantee: given a polynomial-time algorithm constructing a cycle of length \(f(L)\) in an undirected graph \(G\) containing a cycle of length \(L\), their result yields a polynomial-time algorithm constructing a cycle of length \(2δ(G) + Ω(f(k))\), where \(δ(G)\) is the minimum degree of \(G\) and \(k\) is the "offset" \(L - 2δ(G)\).

- Friedrich, Tobias; Göbel, Andreas; Katzmann, Maximilian; Schiller, Leon
**Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs**International Colloquium on Automata, Languages and Programming (ICALP) 2023: 62:1–62:13 - Fomin, Fedor; Golovach, Petr; Sagunov, Danil; Simonov, Kirill
**Approximating Long Cycle Above Dirac’s Guarantee**International Colloquium on Automata, Languages and Programming (ICALP) 2023: 60:1–60:18 - Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin
**Fault-Tolerant ST-Diameter Oracles**International Colloquium on Automata, Languages and Programming (ICALP) 2023: 24:1–24:20