Deligkas, A., Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2026). The complexity of envy-free graph cutting. Artificial Intelligence, 358, Article 104585. https://doi.org/10.1016/j.artint.2026.104585
E192-01 - Forschungsbereich Algorithms and Complexity E056-13 - Fachbereich LogiCS
-
Journal:
Artificial Intelligence
-
ISSN:
0004-3702
-
Date (published):
Sep-2026
-
Number of Pages:
15
-
Publisher:
ELSEVIER
-
Peer reviewed:
Yes
-
Keywords:
Envy-freeness; Fair division; Graph cutting
en
Abstract:
We consider the problem of fairly dividing a set of heterogeneous divisible resources among a set of agents with different preferences. We focus on the case where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy-freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents, and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the input graph. For the latter case, we design a polynomial-time algorithm for the problem when the graph has a constant number of edges.
