2026-07-22T06:32:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20616 2024-08-23T05:50:29Z ddc:004 open_access

On the Complexity of Community-Aware Network Sparsification Herrendorf, Emanuel Komusiewicz, Christian Morawietz, Nils Sommer, Frank parameterized complexity hypergraph support above guarantee parameterization exponential-time-hypothesis In the NP-hard Π-Network Sparsification problem, we are given an edge-weighted graph G, a collection 𝒞 of c subsets of V(G), called communities, and two numbers 𝓁 and b, and the question is whether there exists a spanning subgraph G' of G with at most 𝓁 edges of total weight at most b such that G'[C] fulfills Π for each community C ∈ 𝒞. We study the fine-grained and parameterized complexity of two special cases of this problem: Connectivity NWS where Π is the connectivity property and Stars NWS, where Π is the property of having a spanning star. First, we provide a tight 2^Ω(n²+c)-time running time lower bound based on the ETH for both problems, where n is the number of vertices in G even if all communities have size at most 4, G is a clique, and every edge has unit weight. For the connectivity property, the unit weight case with G being a clique is the well-studied problem of computing a hypergraph support with a minimum number of edges. We then study the complexity of both problems parameterized by the feedback edge number t of the solution graph G'. For Stars NWS, we present an XP-algorithm for t answering an open question by Korach and Stern [Discret. Appl. Math. '08] who asked for the existence of polynomial-time algorithms for t = 0. In contrast, we show for Connectivity NWS that known polynomial-time algorithms for t = 0 [Korach and Stern, Math. Program. '03; Klemz et al., SWAT '14] cannot be extended to larger values of t by showing NP-hardness for t = 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emanuel Herrendorf and Christian Komusiewicz and Nils Morawietz and Frank Sommer 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.60 urn:nbn:de:0030-drops-206169 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.60 eng https://creativecommons.org/licenses/by/4.0/legalcode