{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T21:21:09Z","timestamp":1794604869580,"version":"4.9.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2021\/20","type":"proceedings-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:00:49Z","timestamp":1628679649000},"page":"139-145","source":"Crossref","is-referenced-by-count":8,"title":["The Parameterized Complexity of Connected Fair Division"],"prefix":"10.24963","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eduard","family":"Eiben","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thekla","family":"Hamm","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[{"name":"University of Leeds, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}","theme":"Artificial Intelligence","location":"Montreal, Canada","acronym":"IJCAI-2021","number":"30","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2021,8,19]]},"end":{"date-parts":[[2021,8,27]]}},"container-title":["Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:00:55Z","timestamp":1628679655000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2021\/20"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2021\/20","relation":{},"subject":[],"published":{"date-parts":[[2021,8]]}}}