A parameterized point of view on forming small coalitions

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 (assuming these preferences are symmetric). This scenario is modeled by the extensively studied Coalition Formation problem. Here we study a version of this problem where each team must additionally be of bounded size.

Formally, we are given an edge-weighted graph G and an integer C, and are tasked with deleting edges from G so that each remaining connected component is of order at most C and the sum of the weights of the remaining edges is as big as possible. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT).

Among our positive results, we provide an FPT algorithm parameterized by vc, the vertex cover number of the input graph G. We also provide a polynomial kernel parameterized by vc in the case where all weights are set to one. This raises the question about the existence of a similar result for the case where the edge-weights are arbitrary. We answer negatively to this question, proving that there can be no polynomial kernel parameterized by vc+C for this case, unless the polynomial hierarchy collapses.

This is a joined work with Harmender Gahlawat and Nikolaos Melissinos.