Assigning entities to teams as a hypergraph discovery problem
Guilherme Ferraz de Arruda, Wan He, Nasimeh Heydaribeni, Tara Javidi, Yamir Moreno, Tina Eliassi‐Rad · Communications Physics · 2026
Assigning agents to teams under strict task and effort constraints is crucial in business, science, and engineering, where disruptions can cause significant losses. Current methods do not explore hypergraph-based solutions that explicitly optimize algebraic connectivity under constraints, leaving unresolved how to systematically form robust, recoverable teams. We present a hypergraph-based team assignment algorithm where nodes represent agents and hyperedges represent tasks. The search is guided by input constraints and aims to optimize resilience and diffusion by maximizing the algebraic connectivity of an edge-dependent, vertex-weighted hypergraph. We employ constrained simulated annealing to find a satisfactory hypergraph by enforcing both the minimum effort required for task completion and the maximum effort agents can exert. We evaluate robustness by assessing solution recovery after node removal attacks. Our results demonstrate that the hypergraph formulation yields more robust solutions than the bipartite formulation and the greedy approach. Assigning entities to teams for task completion under constraints is a complex combinatorial optimization challenge. Here, the authors introduce a novel algorithm using hypergraph-based search to optimize resilience and diffusion, demonstrating superior robustness to node removal attacks compared to traditional methods, with implications for diverse fields requiring resilient team configurations