License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.10
URN: urn:nbn:de:0030-drops-173668
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17366/
Ducoffe, Guillaume
Obstructions to Faster Diameter Computation: Asteroidal Sets
Abstract
An extremity is a vertex such that the removal of its closed neighbourhood does not increase the number of connected components. Let Ext_α be the class of all connected graphs whose quotient graph obtained from modular decomposition contains no more than α pairwise nonadjacent extremities. Our main contributions are as follows. First, we prove that the diameter of every m-edge graph in Ext_{α} can be computed in deterministic O(α³ m^{3/2}) time. We then improve the runtime to O(α³m) for bipartite graphs, to O(α⁵m) for triangle-free graphs, O(α³Δm) for graphs with maximum degree Δ, and more generally to linear for all graphs with bounded clique-number. Furthermore, we can compute an additive +1-approximation of all vertex eccentricities in deterministic O(α² m) time. This is in sharp contrast with general m-edge graphs for which, under the Strong Exponential Time Hypothesis (SETH), one cannot compute the diameter in O(m^{2-ε}) time for any ε > 0.
As important special cases of our main result, we derive an O(m^{3/2})-time algorithm for exact diameter computation within dominating pair graphs of diameter at least six, and an O(k³m^{3/2})-time algorithm for this problem on graphs of asteroidal number at most k. Both results extend prior works on exact and approximate diameter computation within AT-free graphs. To the best of our knowledge, this is also the first deterministic subquadratic-time algorithm for computing the diameter within the subclasses of: chordal graphs of bounded leafage (generalizing the interval graphs), k-moplex graphs and k-polygon graphs (generalizing the permutation graphs) for any fixed k. We end up presenting an improved algorithm for chordal graphs of bounded asteroidal number, and a partial extension of our results to the larger class of all graphs with a dominating target of bounded cardinality. Our time upper bounds in the paper are shown to be essentially optimal under plausible complexity assumptions.
Our approach is purely combinatorial, that differs from most prior recent works in this area which have relied on geometric primitives such as Voronoi diagrams or range queries. On our way, we uncover interesting connections between the diameter problem, Lexicographic Breadth-First Search, graph extremities and the asteroidal number.
BibTeX - Entry
@InProceedings{ducoffe:LIPIcs.IPEC.2022.10,
author = {Ducoffe, Guillaume},
title = {{Obstructions to Faster Diameter Computation: Asteroidal Sets}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {10:1--10:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-260-0},
ISSN = {1868-8969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17366},
URN = {urn:nbn:de:0030-drops-173668},
doi = {10.4230/LIPIcs.IPEC.2022.10},
annote = {Keywords: Diameter computation, Asteroidal number, LexBFS}
}
|
Keywords: |
|
Diameter computation, Asteroidal number, LexBFS |
|
Collection: |
|
17th International Symposium on Parameterized and Exact Computation (IPEC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
