ML Anthology

The Densest SWAMP Problem: Subhypergraphs with Arbitrary Monotonic Partial Edge Rewards

Vedangi Bengali, Nikolaj Tatti, Iiro Kumpulainen, Florian Adriaens, Nate Veldt
ECML-PKDD 2025 pp. 75-91
doi:10.1007/978-3-032-06066-2_5 /ecmlpkdd/2025/bengali2025ecmlpkdd-densest/

Abstract

We consider a generalization of the densest subhypergraph problem where nonnegative rewards are given for including partial hyperedges in a dense subhypergraph. Prior work addressed this problem only in cases where reward functions are convex, in which case the problem is poly-time solvable. We consider a broader setting where rewards are monotonic but otherwise arbitrary. We first prove hardness results for a wide class of non-convex rewards, then design a 1/ k -approximation by projecting to the nearest set of convex rewards, where k is the maximum hyperedge size. We also design another 1/ k -approximation using a faster peeling algorithm, which (somewhat surprisingly) differs from the standard greedy peeling algorithm used to approximate other variants of the densest subgraph problem. Our results include an empirical analysis of our algorithm across several real-world hypergraphs.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Bengali et al. "The Densest SWAMP Problem: Subhypergraphs with Arbitrary Monotonic Partial Edge Rewards." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025. doi:10.1007/978-3-032-06066-2_5

Markdown

[Bengali et al. "The Densest SWAMP Problem: Subhypergraphs with Arbitrary Monotonic Partial Edge Rewards." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2025.](https://mlanthology.org/ecmlpkdd/2025/bengali2025ecmlpkdd-densest/) doi:10.1007/978-3-032-06066-2_5

BibTeX

@inproceedings{bengali2025ecmlpkdd-densest,
  title     = {{The Densest SWAMP Problem: Subhypergraphs with Arbitrary Monotonic Partial Edge Rewards}},
  author    = {Bengali, Vedangi and Tatti, Nikolaj and Kumpulainen, Iiro and Adriaens, Florian and Veldt, Nate},
  booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
  year      = {2025},
  pages     = {75-91},
  doi       = {10.1007/978-3-032-06066-2_5},
  url       = {https://mlanthology.org/ecmlpkdd/2025/bengali2025ecmlpkdd-densest/}
}