2026-08-25T17:34:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27139 2026-08-25T13:18:15Z ddc:004 open_access

Advances in Exact and Approximate Group Closeness Centrality Maximization Schulz, Christian Ternes, Jakob Woydt, Henning Group Closeness Centrality Exact Algorithms Approximation Algorithms In the NP-hard Group Closeness Centrality Maximization problem, the input is a graph G = (V,E) and a positive integer k, and the task is to find a set S ⊆ V of size k that minimizes group farness f(S) = ∑_{v ∈ V} min_{s ∈ S} dist(v,s). The state-of-the-art exact algorithm iteratively solves ILPs of increasing size until the final ILP can provably represent an optimal solution. We introduce a new data reduction technique that eliminates variables from the ILP by proving that certain vertices have their distance to any optimal solution structurally determined by a neighbor. Additionally, we bootstrap the exact solver with an approximate solution to produce near-sufficient ILPs from the first iteration, reducing the number of needed iterations. Our improvements yield a speedup by a factor of 4.5 over the next best exact algorithm and can achieve speedups by up to a factor of 34.1. Furthermore, we add reduction techniques to a 1/5-approximation algorithm, and show that these adaptations do not compromise its approximation guarantee. The improved algorithm achieves mean speedups of up to 1.6 and a maximum speedup of 9.6 times. Finally, we settle an open question by proving that a widely used greedy algorithm admits arbitrarily poor approximation ratios. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Schulz and Jakob Ternes and Henning Woydt 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.3 urn:nbn:de:0030-drops-271394 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode