---
title: "The Parameterized Complexity of Connected Fair Division"
authors:
  - "Argyrios Deligkas"
  - "Eduard Eiben"
  - "Robert Ganian"
  - "Thekla Hamm"
  - "Sebastian Ordyniak"
doi: "10.24963/ijcai.2021/20"
url: "https://ijcai.org/proceedings/2021/20"
pdf: "https://ijcai.org/proceedings/2021/0020.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "139-145"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Computational Social Choice"
  - "Agent-based and Multi-agent Systems: Resource Allocation"
---

# The Parameterized Complexity of Connected Fair Division

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

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 139-145. DOI: [10.24963/ijcai.2021/20](https://doi.org/10.24963/ijcai.2021/20)

## Abstract

We study the Connected Fair Division problem (CFD), which generalizes the fundamental problem of fairly allocating resources to agents by requiring that the items allocated to each agent form a connected subgraph in a provided item graph G. We expand on previous results by providing a comprehensive complexity-theoretic understanding of CFD based on several new algorithms and lower bounds while taking into account several well-established notions of fairness: proportionality, envy-freeness, EF1 and EFX. In particular, we show that to achieve tractability, one needs to restrict both the agents and the item graph in a meaningful way. We design (XP)-algorithms for the problem parameterized by (1) clique-width of G plus the number of agents and (2) treewidth of G plus the number of agent types, along with corresponding lower bounds. Finally, we show that to achieve fixed-parameter tractability, one needs to not only use a more restrictive parameterization of G, but also include the maximum item valuation as an additional parameter.