The Densest SWAMP Problem studies how to select a node-set in a hypergraph that maximizes density. This generalizes densest subgraph problem to hypergraphs by allowing each hyperedge to contribute a monotonic reward based on how much of it is captured by the chosen dense node subset. We characterize the problem's complexity landscape, develop scalable approximation algorithms with theoretical guarantees and validate them on real-world datasets.

 Paper | Arxiv | Code   Published at : ECML-PKDD 2025 

Improved hardness and approximations for Cardinality-based minimum s-t cut problems in Hypergraphs: We study hypergraph s–t cut objectives where each hyperedge incurs a cut penalty depending on how many of its nodes lie on each side of the cut. These functions generalize classic cut models, but can often be non-submodular, leading to new computational challenges. We characterize complexity/approximability hardness results and design approximation methods for non-submodular cut functions.

Arxiv | Status: Going through a second revision for a Journal Publication

Fast Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling: We design fast algorithms with provable approximation guarantees for LambdaCC, a flexible graph clustering objective that comes with a tunable parameter. The algorithms are scalable, can be made purely combinatorial, and are built on a new parameterized edge-labeling formulation inspired by strong triadic closure in social networks. We also derive lower bounds that provide a posteriori guarantees for popular heuristics.

Paper | Arxiv | Code | Published at: CIKM - 2023

LambdaCC to discover regulatory genes in gene-expression networks : We apply LambdaCC clustering to gene expression networks to discover co-expressed gene modules and highlight potential 'regulatory genes' associated with module activity. (In progress.)