# Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 65 references that are in the map.
- First posted on arXiv 28 May 2025.

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

- [Fractional Hedonic Games](https://mlsanity.com/paper/1705.10116/) (2017)
- [An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version)](https://mlsanity.com/paper/1901.06862/) (2019)
- [An Improved Parameterized Algorithm for Treewidth](https://mlsanity.com/paper/2211.07154/) (2022)
- [Individual-Based Stability in Hedonic Diversity Games](https://mlsanity.com/paper/1911.08669/) (2019)
- [Hedonic Diversity Games: A Complexity Picture with More than Two Colors](https://mlsanity.com/paper/2202.09210/) (2022)
- [On the Computational Complexity of Vertex Integrity and Component Order Connectivity](https://mlsanity.com/paper/1403.6331/) (2014)
- [Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty](https://mlsanity.com/paper/1509.02424/) (2015)
- [Pareto optimal coalitions of fixed size](https://mlsanity.com/paper/1901.06737/) (2019)
- [Hedonic Games and Treewidth Revisited](https://mlsanity.com/paper/2202.06925/) (2022)
- [Simple Causes of Complexity in Hedonic Games](https://mlsanity.com/paper/1507.03474/) (2015)
- [Partitioning a Graph into Small Pieces with Applications to Path Transversal](https://mlsanity.com/paper/1607.05122/) (2016)
- [Robustness against Agent Failure in Hedonic Games](https://mlsanity.com/paper/1903.05534/) (2019)
- [Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity](https://mlsanity.com/paper/2203.09655/) (2022)
- [Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-like Graphs](https://mlsanity.com/paper/2310.05139/) (2023)

## Built on by (most cited first, 1 of 1)

- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)

## Abstract (arXiv)

Imagine we want to split a group of agents into teams in the most efficient way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied textscCoalition Formation problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded treewidth) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded vertex cover number).