The Complexity of Envy-Free Graph Cutting
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
Abstract
We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting 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 graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.
BibTeX
@inproceedings{ijcai2022p34,
title = {The Complexity of Envy-Free Graph Cutting},
author = {Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Ordyniak, Sebastian},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {237--243},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/34},
url = {https://doi.org/10.24963/ijcai.2022/34},
}