Faster diameter computation in graphs of bounded Euler genus
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913686197633024 |
|---|---|
| author | Kluk, Kacper Pilipczuk, Marcin Pilipczuk, Michał Stamoulis, Giannos |
| author_facet | Kluk, Kacper Pilipczuk, Marcin Pilipczuk, Michał Stamoulis, Giannos |
| contents | We show that for any fixed integer $k \geq 0$, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected $n$-vertex graph of Euler genus at most $k$ in time \[ \mathcal{O}_k(n^{2-\frac{1}{25}}). \] Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most $k$ after deletion of at most $k$ vertices, we show an algorithm for the same task that achieves the running time bound \[ \mathcal{O}_k(n^{2-\frac{1}{356}} \log^{6k} n). \] Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of $K_h$-minor-free graphs, but the running time bound is $\mathcal{O}_h(n^{2-c_h})$ for some constant $c_h > 0$ depending on $h$. That is, our savings in the exponent, as compared to the naive quadratic algorithm, are independent of the parameter $k$. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster diameter computation in graphs of bounded Euler genus Kluk, Kacper Pilipczuk, Marcin Pilipczuk, Michał Stamoulis, Giannos Data Structures and Algorithms Combinatorics We show that for any fixed integer $k \geq 0$, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected $n$-vertex graph of Euler genus at most $k$ in time \[ \mathcal{O}_k(n^{2-\frac{1}{25}}). \] Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most $k$ after deletion of at most $k$ vertices, we show an algorithm for the same task that achieves the running time bound \[ \mathcal{O}_k(n^{2-\frac{1}{356}} \log^{6k} n). \] Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of $K_h$-minor-free graphs, but the running time bound is $\mathcal{O}_h(n^{2-c_h})$ for some constant $c_h > 0$ depending on $h$. That is, our savings in the exponent, as compared to the naive quadratic algorithm, are independent of the parameter $k$. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus. |
| title | Faster diameter computation in graphs of bounded Euler genus |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2502.07501 |