The Complexity of Envy-Free Graph Cutting

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Thekla Hamm, Sebastian Ordyniak
12/12/2023
cs.DScs.AIcs.CC

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Graphical House Allocation

85% match2023

Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division

84% match2024

Cutsets and EF1 Fair Division of Graphs

83% match2024

On Approximate MMS Allocations on Restricted Graph Classes

83% match2025

The Multi-Stage Assignment Problem: A Fairness Perspective

82% match2025

Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions

81% match2025

Cite this paper

@article{deligkas2023complexity,
  title  = {The Complexity of Envy-Free Graph Cutting},
  author = {Argyrios Deligkas and Eduard Eiben and Robert Ganian and Thekla Hamm and Sebastian Ordyniak},
  year   = {2023},
  eprint = {2312.07043},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2312.07043v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2312.07043.svg)](https://codeofpaper.com/paper/2312.07043)

Discussion