mlsanityData to 7 Oct 2026

The Complexity of Envy-Free Graph Cutting

arXiv 2312.07043 ↗First posted 12 Dec 2023cs.DS cs.AI cs.CCcited by 0

Not on the map. Why?

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.

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

Builds on

24 of 62 references.

References · 24

  1. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  2. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  3. 2019Refined Complexity of PCA with Outlierscited by 7
  4. 2016Fair Division via Social Comparisoncited by 5
  5. 2017Fair Division of a Graphcited by 4
  6. 2020Fair Division of Time: Multi-layered Cake Cuttingcited by 4
  7. 2021Envy-free division of multi-layered cakescited by 4
  8. 2018Almost Envy-Free Allocations with Connected Bundlescited by 3
  9. 2018Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraintscited by 3
  10. 2019Contiguous Cake Cutting: Hardness Results and Approximation Algorithmscited by 3
  11. 2017Deterministic, Strategyproof, and Fair Cake Cuttingcited by 2
  12. 2017Fairly Allocating Contiguous Blocks of Indivisible Itemscited by 2
12 more
  1. 2019Fair and Efficient Cake Division with Connected Piecescited by 2
  2. 2019The Price of Connectivity in Fair Divisioncited by 2
  3. 2017Networked Fairness in Cake Cuttingcited by 1
  4. 2017Communication Complexity of Cake Cuttingcited by 1
  5. 2019Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocolcited by 1
  6. 2019Dividing a Graphical Cakecited by 1
  7. 2020How to Cut a Cake Fairly: A Generalization to Groupscited by 1
  8. 2020Mind the Gap: Cake Cutting With Separationcited by 1
  9. 2021Fair division of graphs and of tangled cakescited by 1
  10. 2021Graphical Cake Cutting via Maximin Sharecited by 1
  11. 2021Keep Your Distance: Land Division With Separationcited by 1
  12. 2023Approximate Envy-Freeness in Graphical Cake Cuttingcited by 1

Built on by

Not cited yet.