The Complexity of Envy-Free Graph Cutting
Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Argyrios Deligkas1 , Eduard Eiben1 , Robert Ganian2 , Thekla Hamm2 , Sebastian Ordyniak3 1Royal Holloway, University of London, UK 2TU Wien, Austria 3University of Leeds, UK {argyrios.deligkas,eduard.eiben}@rhul.ac.uk, {rganian, thekla.hamm,sordyniak}@gmail.com |
| Pseudocode | No | No structured pseudocode or algorithm blocks were found in the paper. |
| Open Source Code | No | The paper presents theoretical results on complexity and algorithm design and does not mention releasing any source code. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers for experimental reproducibility. It mentions Linear Programming but no specific solver. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |