Guillaume Ducoffe ; Michel Habib ; Laurent Viennot - Fast Diameter Computation within Split Graphs

dmtcs:6422 - Discrete Mathematics & Theoretical Computer Science, November 15, 2021, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.6422
Fast Diameter Computation within Split GraphsArticle

Authors: Guillaume Ducoffe ; Michel Habib ORCID; Laurent Viennot

    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.


    Volume: vol. 23, no. 3
    Section: Graph Theory
    Published on: November 15, 2021
    Accepted on: September 10, 2021
    Submitted on: April 23, 2020
    Keywords: Computer Science - Data Structures and Algorithms,Mathematics - Combinatorics
    Funding:
      Source : OpenAIRE Graph
    • Scalable routing in Multi-Modal transportation networks; Funder: French National Research Agency (ANR); Code: ANR-17-CE22-0016
    • Metric graph theory; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0015
    • Incentive - UI 3 - 2013; Funder: Fundação para a Ciência e a Tecnologia, I.P.; Code: Incentivo/FIS/UI0003/2013

    2 Documents citing this article

    Consultation statistics

    This page has been seen 577 times.
    This article's PDF has been downloaded 357 times.