2026-07-22T00:05:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15399 2024-03-06T10:55:39Z ddc:004 open_access

Optimal Centrality Computations Within Bounded Clique-Width Graphs Ducoffe, Guillaume Clique-width Centralities computation Facility Location problems Distance-labeling scheme Fine-grained complexity in P Graph theory Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known 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 run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O(klog²{n}) bits per vertex and constructible in Õ(k(n+m)) time from a given k-expression. 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 All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Ducoffe 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.16 urn:nbn:de:0030-drops-153995 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.16 eng https://creativecommons.org/licenses/by/4.0/legalcode