%0 Conference Paper %1 fink+spoerhase:mbc-approx-tract %A Fink, Martin %A Spoerhase, Joachim %B Proc. Workshop Algorithms Comp. (WALCOM'11) %C Berlin, Heidelberg %D 2011 %E Katoh, Naoki %E Kumar, Amit %I Springer %K approximability betweenness centrality maximum myown %P 9--20 %T Maximum Betweenness Centrality: Approximability and Tractable Cases %U http://dx.doi.org/10.1007/978-3-642-19094-0_4 %V 6552 %X The Maximum Betweenness Centrality problem (MBC) can be defined as follows. Given a graph find a $k$-element node set $C$ that maximizes the probability of detecting communication between a pair of nodes $s$ and $t$ chosen uniformly at random. It is assumed that the communication between $s$ and $t$ is realized along a shortest $s$--$t$ path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of $C$. Recently, Dolev et al. (2009) showed that MBC is NP-hard and gave a $(1-1/e)$-approximation using a greedy approach. We provide a reduction of MBC to Maximum Coverage that simplifies the analysis of the algorithm of Dolev et al. considerably. Our reduction allows us to obtain a new algorithm with the same approximation ratio for a (generalized) budgeted version of MBC. We provide tight examples showing that the analyses of both algorithms are best possible. Moreover, we prove that MBC is APX-complete and provide an exact polynomial-time algorithm for MBC on tree graphs.

@inproceedings{fink+spoerhase:mbc-approx-tract, abstract = {The Maximum Betweenness Centrality problem (MBC) can be defined as follows. Given a graph find a $k$-element node set $C$ that maximizes the probability of detecting communication between a pair of nodes $s$ and $t$ chosen uniformly at random. It is assumed that the communication between $s$ and $t$ is realized along a shortest $s$--$t$ path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of $C$. Recently, Dolev et al. (2009) showed that MBC is NP-hard and gave a $(1-1/e)$-approximation using a greedy approach. We provide a reduction of MBC to Maximum Coverage that simplifies the analysis of the algorithm of Dolev et al. considerably. Our reduction allows us to obtain a new algorithm with the same approximation ratio for a (generalized) budgeted version of MBC. We provide tight examples showing that the analyses of both algorithms are best possible. Moreover, we prove that MBC is APX-complete and provide an exact polynomial-time algorithm for MBC on tree graphs.}, added-at = {2011-06-07T14:13:40.000+0200}, address = {Berlin, Heidelberg}, author = {Fink, Martin and Spoerhase, Joachim}, biburl = {https://www.bibsonomy.org/bibtex/25631dceacd25a8ad964fc69e2ce688e9/fink}, booktitle = {Proc. Workshop Algorithms Comp. (WALCOM'11)}, editor = {Katoh, Naoki and Kumar, Amit}, interhash = {cdb30daff8b91530b533690875d7a49c}, intrahash = {5631dceacd25a8ad964fc69e2ce688e9}, keywords = {approximability betweenness centrality maximum myown}, pages = {9--20}, pdf = {http://www1.informatik.uni-wuerzburg.de/pub/fink/mbc.pdf}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, slides = {http://www1.informatik.uni-wuerzburg.de/pub/slides/mbc-slides.pdf}, timestamp = {2013-06-17T10:53:40.000+0200}, title = {Maximum Betweenness Centrality: Approximability and Tractable Cases}, url = {http://dx.doi.org/10.1007/978-3-642-19094-0_4}, volume = 6552, year = 2011 }