 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.59
URN: urn:nbn:de:0030-drops-115555
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11555/
 Go to the corresponding LIPIcs Volume Portal

### Minimizing and Computing the Inverse Geodesic Length on Trees

 pdf-format:

### Abstract

For any fixed measure H that maps graphs to real numbers, the MinH problem is defined as follows: given a graph G, an integer k, and a target tau, is there a set S of k vertices that can be deleted, so that H(G - S) is at most tau? In this paper, we consider the MinH problem on trees. We call H balanced on trees if, whenever G is a tree, there is an optimal choice of S such that the components of G - S have sizes bounded by a polynomial in n / k. We show that MinH on trees is Fixed-Parameter Tractable (FPT) for parameter n / k, and furthermore, can be solved in subexponential time, and polynomial space, whenever H is additive, balanced on trees, and computable in polynomial time. A particular measure of interest is the Inverse Geodesic Length (IGL), which is used to gauge the efficiency and connectedness of a graph. It is defined as the sum of inverse distances between every two vertices: IGL(G) = sum_{{u,v} subseteq V} 1/d_G(u,v). While MinIGL is W-hard for parameter treewidth, and cannot be solved in 2^{o(k + n + m)} time, even on bipartite graphs with n vertices and m edges, the complexity status of the problem remains open in the case where G is a tree. We show that IGL is balanced on trees, to give a 2^O((n log n)^(5/6)) time, polynomial space algorithm. The distance distribution of G is the sequence {a_i} describing the number of vertex pairs distance i apart in G: a_i = |{{u, v}: d_G(u, v) = i}|. Given only the distance distribution, one can easily determine graph parameters such as diameter, Wiener index, and particularly, the IGL. We show that the distance distribution of a tree can be computed in O(n log^2 n) time by reduction to polynomial multiplication. We also extend the result to graphs with small treewidth by showing that the first p values of the distance distribution can be computed in 2^(O(tw(G))) n^(1 + epsilon) sqrt(p) time, and the entire distance distribution can be computed in 2^(O(tw(G))) n^{1 + epsilon} time, when the diameter of G is O(n^epsilon') for every epsilon' > 0.

### BibTeX - Entry

```@InProceedings{gaspers_et_al:LIPIcs:2019:11555,
author =	{Serge Gaspers and Joshua Lau},
title =	{{Minimizing and Computing the Inverse Geodesic Length on Trees}},
booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages =	{59:1--59:19},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-130-6},
ISSN =	{1868-8969},
year =	{2019},
volume =	{149},
editor =	{Pinyan Lu and Guochuan Zhang},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 