# The Complexity of Envy-Free Graph Cutting

arXiv: https://arxiv.org/abs/2312.07043 · HTML: https://mlsanity.com/paper/2312.07043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 12 Dec 2023.

## Builds on (most cited first, 24 of 24)

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Fair Division via Social Comparison](https://mlsanity.com/paper/1611.06589/) (2016)
- [Fair Division of a Graph](https://mlsanity.com/paper/1705.10239/) (2017)
- [Almost Envy-Free Allocations with Connected Bundles](https://mlsanity.com/paper/1808.09406/) (2018)
- [Contiguous Cake Cutting: Hardness Results and Approximation Algorithms](https://mlsanity.com/paper/1911.05416/) (2019)
- [Fair Division of Time: Multi-layered Cake Cutting](https://mlsanity.com/paper/2004.13397/) (2020)
- [Envy-free division of multi-layered cakes](https://mlsanity.com/paper/2106.02262/) (2021)
- [Fairly Allocating Contiguous Blocks of Indivisible Items](https://mlsanity.com/paper/1707.00345/) (2017)
- [Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints](https://mlsanity.com/paper/1811.04872/) (2018)
- [Deterministic, Strategyproof, and Fair Cake Cutting](https://mlsanity.com/paper/1705.06306/) (2017)
- [Fair and Efficient Cake Division with Connected Pieces](https://mlsanity.com/paper/1907.11019/) (2019)
- [The Price of Connectivity in Fair Division](https://mlsanity.com/paper/1908.05433/) (2019)
- [Networked Fairness in Cake Cutting](https://mlsanity.com/paper/1707.02033/) (2017)
- [Communication Complexity of Cake Cutting](https://mlsanity.com/paper/1709.09876/) (2017)
- [Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol](https://mlsanity.com/paper/1907.05083/) (2019)
- [Dividing a Graphical Cake](https://mlsanity.com/paper/1910.14129/) (2019)
- [How to Cut a Cake Fairly: A Generalization to Groups](https://mlsanity.com/paper/2001.03327/) (2020)
- [Mind the Gap: Cake Cutting With Separation](https://mlsanity.com/paper/2012.06682/) (2020)
- [Fair division of graphs and of tangled cakes](https://mlsanity.com/paper/2102.08560/) (2021)
- [Graphical Cake Cutting via Maximin Share](https://mlsanity.com/paper/2105.04755/) (2021)
- [Keep Your Distance: Land Division With Separation](https://mlsanity.com/paper/2105.06669/) (2021)
- [Approximate Envy-Freeness in Graphical Cake Cutting](https://mlsanity.com/paper/2304.11659/) (2023)

## Abstract (arXiv)

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.