Gaspers, Serge ;
Lau, Joshua
Minimizing and Computing the Inverse Geodesic Length on Trees
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 FixedParameter 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[1]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:159:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11555},
URN = {urn:nbn:de:0030drops115555},
doi = {10.4230/LIPIcs.ISAAC.2019.59},
annote = {Keywords: Trees, Treewidth, FixedParameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution}
}
28.11.2019
Keywords: 

Trees, Treewidth, FixedParameter Tractability, Inverse Geodesic Length, Vertex deletion, Polynomial multiplication, Distance distribution 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 