Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Beyond Helly graphs: the diameter problem on absolute retracts

Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-03106688
Contributor : Guillaume Ducoffe <>
Submitted on : Tuesday, January 12, 2021 - 5:25:11 AM
Last modification on : Tuesday, January 12, 2021 - 5:25:11 AM

Links full text

Identifiers

  • HAL Id : hal-03106688, version 1
  • ARXIV : 2101.03574

Citation

Guillaume Ducoffe. Beyond Helly graphs: the diameter problem on absolute retracts. 2021. ⟨hal-03106688⟩

Share

Metrics

Record views

20