# The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks

arXiv: https://arxiv.org/abs/2604.21537 · HTML: https://mlsanity.com/paper/2604.21537/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 32 references that are in the map.
- First posted on arXiv 23 Apr 2026.

## Builds on (most cited first, 5 of 5)

- [A Survey on Influence Maximization in a Social Network](https://mlsanity.com/paper/1808.05502/) (2018)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [A Novel Approach for Estimating Truck Factors](https://mlsanity.com/paper/1604.06766/) (2016)
- [Game-theoretic Network Centrality: A Review](https://mlsanity.com/paper/1801.00218/) (2017)
- [Bus Factor In Practice](https://mlsanity.com/paper/2202.01523/) (2022)

## Abstract (arXiv)

Identifying critical nodes in complex networks is a fundamental task in graph mining. Yet, methods addressing an all-or-nothing coverage mechanics in a bipartite dependency network, a graph with two types of nodes where edges represent dependency relationships across the two groups only, remain largely unexplored. We formalize the CriticalSet problem: given an arbitrary bipartite graph modeling dependencies of items on contributors, identify the set of k contributors whose removal isolates the largest number of items. We prove that this problem is NP-hard and requires maximizing a supermodular set function, for which standard forward greedy algorithms provide no approximation guarantees. Consequently, we model CriticalSet as a coalitional game, deriving a closed-form centrality, ShapleyCov, based on the Shapley value. This measure can be interpreted as the expected number of items isolated by a contributor's departure. Leveraging these insights, we propose MinCov, a linear-time iterative peeling algorithm that explicitly accounts for connection redundancy, prioritizing contributors who uniquely support many items. Extensive experiments on synthetic and large-scale real datasets, including a Wikipedia graph with over 250 million edges, reveal that MinCov and ShapleyCov significantly outperform traditional baselines. Notably, MinCov achieves near-optimal performance, within 0.02 AUC of a Stochastic Hill Climbing metaheuristic, while remaining several orders of magnitude faster.