Skip to Main content Skip to Navigation
New interface
Conference papers

Fast Diameter Computation within Split Graphs

Abstract : When can we compute the diameter of a graph in quasi linear time? We address this question for the class of 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 subclasses of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded 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 VC-dimension and the 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 = \mathcal{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 complements of $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k = \mathcal{O}(1)$, and even in time $\mathcal{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 boundedtreewidth 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.
Complete list of metadata

https://hal.inria.fr/hal-03373614
Contributor : Laurent Viennot Connect in order to contact the contributor
Submitted on : Monday, October 11, 2021 - 3:37:09 PM
Last modification on : Friday, September 16, 2022 - 1:16:06 PM

Links full text

Identifiers

  • HAL Id : hal-03373614, version 1
  • ARXIV : 1910.03438

Collections

Citation

Guillaume Ducoffe, Michel Habib, Laurent Viennot. Fast Diameter Computation within Split Graphs. COCOA 2019 - 13th Annual International Conference on Combinatorial Optimization and Applications, Dec 2019, Xiamen, China. ⟨hal-03373614⟩

Share

Metrics

Record views

19