On the Group Coverage Centrality Problem: Parameterized Complexity and Heuristics

Society for Industrial and Applied Mathematics eBooks, pp. 13–24

Abstract

We study the problem of computing a group of k vertices that covers a maximum number of shortest paths in a graph in the context of network centrality. In Group Coverage Centrality the input is an undirected graph G = (V, E) and the aim is to find a set S of κ vertices such that the number of vertex pairs {u,v} covered by S is at least t, if such a set exists. Here, S covers a vertex pair {u,v} if S contains at least one internal vertex of some shortest (u,v)-path. Also, we study All Pairs Coverage, the special case of Group Coverage Centrality where we want to cover at least one shortest path for all non-adjacent vertex pairs. We study the parameterized complexity of Group Coverage Centrality and All Pairs Coverage for the solution-size related parameters κ and |V| — κ, structural graph parameters, and t. On the negative side, we show that solution-size parameterizations do not lead to FPT-algorithms. On the positive side, we show that additionally considering structural parameters motivated from social network theory leads to FPT- algorithms for All Pairs Coverage and that Group Coverage Centrality admits FPT-algorithms for t and for t — k. On the practical side, we introduce several heuristics and compare their performance on standard benchmark graphs. We show that a greedy Set Cover- based heuristic gives almost-optimal results while a simple degree-based heuristic performs only slightly worse with a much better running time. *Work done while all authors were affiliated with Philipps-Universität Marburg, Germany. Some of the results of this work are also contained in the second author's Bachelor thesis [35].

Authors 3

1. Christian Komusiewicz Aachen

   RWTH Aachen University · Philipps University of Marburg · Friedrich Schiller University Jena

   Affiliation as printed

   Friedrich-Schiller-Universität, Jena, Germany, c. komusiewicz@uni-jena.de

   Philipps-Universität Marburg, Germany, fsommer@informatik.uni-marburg.de

   RWTH Aachen University, Germany jannis.schramek@rwth-aachen.de

2. Jannis Schramek Aachen

   RWTH Aachen University · Philipps University of Marburg · Friedrich Schiller University Jena

   Affiliation as printed

   Friedrich-Schiller-Universität, Jena, Germany, c. komusiewicz@uni-jena.de

   Philipps-Universität Marburg, Germany, fsommer@informatik.uni-marburg.de

   RWTH Aachen University, Germany jannis.schramek@rwth-aachen.de

3. Frank O. Sommer Aachen

   RWTH Aachen University · Philipps University of Marburg · Friedrich Schiller University Jena

   Affiliation as printed

   Friedrich-Schiller-Universität, Jena, Germany, c. komusiewicz@uni-jena.de

   Philipps-Universität Marburg, Germany, fsommer@informatik.uni-marburg.de

   RWTH Aachen University, Germany jannis.schramek@rwth-aachen.de