On the Complexity of Community-Aware Network Sparsification

Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, Frank Sommer

Introduction

Network sparsification is a fundamental technique in graph theory and data analysis, aimed at reducing the number of edges in a graph while preserving its essential structural properties. While traditional methods focus on global properties like distances or cuts, many real-world networks possess a rich internal structure defined by "communities"—overlapping subsets of vertices representing functional units. This paper explores the complexity of community-aware network sparsification ($\Pi$-NWS), where the goal is to find a minimal edge set that satisfies a specific property $\Pi$ for every predefined community.

The $\Pi$-NWS Problem

The authors investigate two primary properties within this framework:

  1. Connectivity NWS: Each community must remain a connected subgraph in the sparsified network.
  2. Stars NWS: Each community must contain a spanning star—a single "center" node connected to all other members of that community.
Figure 1: Illustration of community-aware sparsification where communities (blue) must maintain specific internal structures in the sparsified graph (red edges).

While previous literature often restricted solutions to "tree supports" (acyclic graphs), this work delves into the more general case where the solution graph may contain cycles, significantly increasing the problem's complexity.

Complexity Landscape and Hardness

A central contribution of this research is mapping the complexity landscape of these problems. Using the Exponential Time Hypothesis (ETH), the authors establish a formidable lower bound of $2^{\Omega(n^2+c)}$ for the general case, where $n$ is the number of vertices and $c$ is the number of communities. This suggests that brute-force approaches are near-optimal for the most general problem instances.

The study reveals a sharp "complexity dichotomy" based on the feedback edge number ($t$), which measures the number of edges that must be removed to make the solution acyclic. For Connectivity NWS, the problem is solvable in polynomial time when $t=0$ (tree solutions) but becomes NP-hard as soon as $t=1$. In contrast, Stars NWS remains solvable in polynomial time for any constant $t$.

Figure 4: Gadgets used in the hardness reductions from logic problems to demonstrate the complexity of finding optimal sparsified supports.

To prove these hardness results, the authors employ reductions from classic NP-complete problems such as 3-SAT and Hitting Set, constructing intricate gadgets where community structures enforce logical constraints.

Algorithmic Breakthroughs

For the Stars NWS problem, the authors present a novel XP-algorithm that runs in $m^{4t} \cdot \text{poly}(|I|)$ time. This result is significant as it provides the first polynomial-time algorithm for finding optimal star-based solutions that are not restricted to trees. The algorithm leverages the concept of "center twins"—vertices belonging to the same set of communities—to effectively prune the search space for potential star centers.

Furthermore, the authors identify that Unweighted Stars NWS is Fixed-Parameter Tractable (FPT) with respect to the number of communities $c$. However, they prove that adding edge weights makes the problem significantly harder (W[1]-hard), highlighting the sensitivity of these problems to edge costs and community overlap.

Conclusion and Future Directions

This work provides a comprehensive theoretical foundation for community-aware network sparsification. By moving beyond tree-based solutions, the authors have uncovered a nuanced complexity landscape where the choice of property $\Pi$ and the allowed cyclicity $t$ drastically alter the difficulty of the task. Future research may focus on closing the gap between current lower and upper bounds for the unweighted case or extending the framework to other graph properties like bounded diameter or $k$-connectivity within communities.

Summary updated

Abstract

Network sparsification is the task of reducing the number of edges of a given graph while preserving some crucial graph property. In community-aware network sparsification, the preserved property concerns the subgraphs that are induced by the communities of the graph which are given as vertex subsets. This is formalized in the $\Pi$-Network Sparsification problem: given an edge-weighted graph $G$, a collection $Z$ of $c$ subsets of $V(G)$ (communities), and two numbers $\ell, b$, the question is whether there exists a spanning subgraph $G'$ of $G$ with at most $\ell$ edges of total weight at most $b$ such that $G'[C]$ fulfills $\Pi$ for each community $C$. Here, we consider two graph properties $\Pi$: the connectivity property (Connectivity NWS) and the property of having a spanning star (Stars NWS). Since both problems are NP-hard, we study their parameterized and fine-grained complexity. We provide a tight $2^{\Omega(n^2+c)} poly(n+|Z|)$-time running time lower bound based on the ETH for both problems, where $n$ is the number of vertices in $G$. The lower bound holds even in the restricted case when 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$. This answers an open question by Korach and Stern [Disc. 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 by showing that Connectivity NWS is NP-hard for $t=1$.
BibTeX
@inproceedings{herrendorf2024complexity,
  author = {Emanuel Herrendorf and Christian Komusiewicz and Nils Morawietz and Frank Sommer},
  title = {{On the Complexity of Community-Aware Network Sparsification}},
  booktitle = {MFCS},
  year = {2024},
  doi = {10.4230/lipics.mfcs.2024.60},
}
Figure