Fast Diameter Computation within Split Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2021

Fast Diameter Computation within Split Graphs

Résumé

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either $2$ or $3$, under the Strong Exponential-Time Hypothesis (SETH) we cannot compute the diameter of an $n$-vertex $m$-edge split graph in less than quadratic time -- in the size $n+m$ of the input. Therefore it is worth to study the complexity of diameter computation on {\em subclasses} of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded {\em clique-interval number} and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the {\em VC-dimension} and the {\em stabbing number} of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: - For the $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k={\cal O}(1)$, and even in quasi linear time if $k=o(\log{n})$ and in addition a corresponding ordering of the vertices in the clique is given. However, under SETH this cannot be done in truly subquadratic time for any $k = \omega(\log{n})$. - For the {\em complements} of $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k={\cal O}(1)$, and even in time ${\cal O}(km)$ if a corresponding ordering of the vertices in the stable set is given. Again this latter result is optimal under SETH up to polylogarithmic factors. Our findings raise the question whether a $k$-clique interval ordering can always be computed in quasi linear time. We prove that it is the case for $k=1$ and for some subclasses such as bounded-treewidth split graphs, threshold graphs and comparability split graphs. Finally, we prove that some important subclasses of split graphs -- including the ones mentioned above -- have a bounded clique-interval number.
Fichier principal
Vignette du fichier
DHV-dmtcs.pdf (210.47 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02307397 , version 1 (07-10-2019)
hal-02307397 , version 2 (20-04-2020)
hal-02307397 , version 3 (20-05-2021)
hal-02307397 , version 4 (11-10-2021)

Identifiants

Citer

Guillaume Ducoffe, Michel Habib, Laurent Viennot. Fast Diameter Computation within Split Graphs. Discrete Mathematics and Theoretical Computer Science, 2021, ⟨10.46298/dmtcs.6422⟩. ⟨hal-02307397v4⟩
188 Consultations
322 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More