The Complexity of Envy-Free Graph Cutting

Deligkas, Argyrios; Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Ordyniak, Sebastian

doi:10.24963/ijcai.2022/34

Record link:

http://hdl.handle.net/20.500.12708/136181

Title:

The Complexity of Envy-Free Graph Cutting

Citation:

Deligkas, A., Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2022). The Complexity of Envy-Free Graph Cutting. In L. De Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (pp. 237–243). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2022/34

CatalogPlus:

AC17204108

Publisher DOI:

10.24963/ijcai.2022/34

Publication Type:

Inproceedings - Full-Paper Contribution

Language:

English

Authors:

Deligkas, Argyrios
Eiben, Eduard
Ganian, Robert
Hamm, Thekla
Ordyniak, Sebastian

Organisational Unit:

E192-01 - Forschungsbereich Algorithms and Complexity

Published in:

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence

ISBN:

978-1-956792-00-3

DOI of the book:

10.24963/ijcai.2022

Date (published):

2022

Event name:

Thirty-First International Joint Conference on Artificial Intelligence

Event date:

23-Jul-2022 - 29-Jul-2022

Event place:

Vienna, Austria

Number of Pages:

Publisher:

International Joint Conferences on Artificial Intelligence

Peer reviewed:

Yes

Keywords:

Agent-based and Multi-agent Systems; Resource Allocation; Computational Social Choice

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.

Project title:

New Frontiers for Parameterized Complexity: P31336-N35 (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
Parameterisierte Analyse in der Künstlichen Intelligenz: Y1329-N (Fonds zur Förderung der wissenschaftlichen Forschung (FWF))

Project (external):

Austrian Science Fund (FWF)
EPSRC

Project ID:

W1255-N23
EP/V00252X/1

Link (external):

https://www.ijcai.org/proceedings/2022/video/34

Research Areas:

Logic and Computation: 100%

Science Branch:

1020 - Informatik: 100%

License:

In Copyright