The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916795034632192 |
|---|---|
| author | Bengali, Vedangi Tatti, Nikolaj Kumpulainen, Iiro Adriaens, Florian Veldt, Nate |
| author_facet | Bengali, Vedangi Tatti, Nikolaj Kumpulainen, Iiro Adriaens, Florian Veldt, Nate |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12998 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards Bengali, Vedangi Tatti, Nikolaj Kumpulainen, Iiro Adriaens, Florian Veldt, Nate Data Structures and Algorithms 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. |
| title | The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.12998 |