A Centrality Problem based on Communication Detection
02/18/2011In centrality problems we search for a set of nodes of a graph that - as a group - is located as central as possible. At the conference WALCOM'11, Martin Fink presents algorithms and additional results for the centrality problem "Maximum Betweenness Centrality", which he investigated together with Spoerhase.
In this problem we are given a graph whose nodes are assigned different weights. We want to find a group of nodes, subject to a budget constraint, that maximizes the probability of detecting communication in the graph. This probability is the probability that at least one of the nodes lies on a randomly chosen shortest path between a pair of vertices that is also chosen at random.
So far, only the unit cost version of this problem had been investigated; even this simpler version is known to be NP-complete and there exists a (1-1/e)-approximate algorithm (Dolev et al., 09). Martin Fink and Joachim Spoerhase developed an algorithm that approximates also the general version of the problem with an approximation factor of 1-1/e and showed that the analyses of the approximation factors of both algorithms are best possible. Additionally they showed that Maximum Betweenness Centrality does not admit a polynomial time approximation scheme, which means that an arbitrarily good approximation cannot be found in polynomial time. Finally, they gave a polynomial time algorithm for solving the problem optimally on tree graphs.
More information can be found in the conference article and the slides of the talk.
