Parameterized Complexity of Edge-Constrained Graph Partitioning

Suppose that we want to divide a set of players into fair teams. Some pairs of players are compatible, and the utility of a team is measured by the number of compatible pairs within it. To ensure fairness, we require every team to achieve a prescribed minimum utility. This gives rise to the Edge-Constrained Graph Partitioning problem: given a graph G and integers r and γ, can we partition the vertices of G into r parts such that every part induces at least γ edges? We also consider the balanced version, in which all parts must have the same size.

In this talk, I will discuss the parameterized complexity of these problems with respect to r, γ, and several structural graph parameters. The results reveal a varied complexity landscape. In particular, the balanced problem admits a polynomial kernel parameterized by r + γ, obtained using matching and expansion arguments. We also give fixed-parameter algorithms parameterized by deletion distance to paths plus γ, and by treedepth plus γ. These results are complemented by hardness results for several combinations of structural parameters, including W[1]-hardness parameterized by γ even on disjoint unions of caterpillars.

The talk will focus on the main combinatorial ideas behind the algorithms, kernelization, and hardness results. This is joint work with Jan Pokorný and Tomáš Valla.