Abstract
Given an nvertex medge graph G of cliquewidth at most k, and a corresponding kexpression, we present algorithms for computing some wellknown centrality indices (eccentricity and closeness) that run in O(2^{O(k)}(n+m)^{1+ε}) time for any ε > 0. Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our runtimes match conditional lower bounds of Coudert et al. (SODA'18) under the Strong ExponentialTime Hypothesis. On our way, we get a distancelabeling scheme for nvertex medge graphs of cliquewidth at most k, using O(klog²{n}) bits per vertex and constructible in Õ(k(n+m)) time from a given kexpression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an Õ(kn²)time algorithm for computing AllPairs ShortestPaths on nvertex graphs of cliquewidth at most k, being given a kexpression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with nonnegative vertexweights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest.
BibTeX  Entry
@InProceedings{ducoffe:LIPIcs.IPEC.2021.16,
author = {Ducoffe, Guillaume},
title = {{Optimal Centrality Computations Within Bounded CliqueWidth Graphs}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {16:116:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15399},
URN = {urn:nbn:de:0030drops153995},
doi = {10.4230/LIPIcs.IPEC.2021.16},
annote = {Keywords: Cliquewidth, Centralities computation, Facility Location problems, Distancelabeling scheme, Finegrained complexity in P, Graph theory}
}
Keywords: 

Cliquewidth, Centralities computation, Facility Location problems, Distancelabeling scheme, Finegrained complexity in P, Graph theory 
Collection: 

16th International Symposium on Parameterized and Exact Computation (IPEC 2021) 
Issue Date: 

2021 
Date of publication: 

22.11.2021 