Efficient Algorithms for Group Centrality (EAGR)

• Applicant: Professor Dr. Christian Komusiewicz
• Subject Area: Theoretical Computer Science
• Term: from 2021 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 450925233

Group Centrality problems are used to identify groups of important actors in social networks. Computing optimal solutions for Group Centrality problems is algorithmically hard an thus these problems are usually solved by heuristic methods. The research projectEAGR investigates whether there are efficient algorithms that solve these problems optimally on real-world instances. To this end, the project aims at the development of algorithms with improved worst-case running times and efficient implementations.To reach improved algorithms, it shall be investigated how the structure of input networks influences the algorithmic difficulty of the problem: Are there network properties that can be exploited algorithmically or do Group Centrality problems remain hard even on veryrestricted instances? On the practical side it shall be investigated, whether an existing software framework for solving hard subgraph problems can be extended to Group Centrality problems which are algorithmically even more challenging.

• DFG Programme: Research Grants