Beyond Helly graphs: the diameter problem on absolute retracts - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2021

Beyond Helly graphs: the diameter problem on absolute retracts

Résumé

Characterizing the graph classes such that, on $n$-vertex $m$-edge graphs in the class, we can compute the diameter faster than in $O(nm)$ time is an important research problem both in theory and in practice. We here make a new step in this direction, for some metrically defined graph classes. Specifically, a subgraph $H$ of a graph $G$ is called a retract of $G$ if it is the image of some idempotent endomorphism of $G$. Two necessary conditions for $H$ being a retract of $G$ is to have $H$ is an isometric and isochromatic subgraph of $G$. We say that $H$ is an absolute retract of some graph class $\mathcal{C}$ if it is a retract of any $G \in \mathcal{C}$ of which it is an isochromatic and isometric subgraph. In this paper, we study the complexity of computing the diameter within the absolute retracts of various hereditary graph classes. First, we show how to compute the diameter within absolute retracts of bipartite graphs in randomized $\tilde{O}(m\sqrt{n})$ time. For the special case of chordal bipartite graphs, it can be improved to linear time, and the algorithm even computes all the eccentricities. Then, we generalize these results to the absolute retracts of $k$-chromatic graphs, for every fixed $k \geq 3$. Finally, we study the diameter problem within the absolute retracts of planar graphs and split graphs, respectively.

Dates et versions

hal-03106688 , version 1 (12-01-2021)

Identifiants

Citer

Guillaume Ducoffe. Beyond Helly graphs: the diameter problem on absolute retracts. 2021. ⟨hal-03106688⟩
34 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More