{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T23:31:03Z","timestamp":1725147063892},"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":[[2022,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2022\/34","type":"proceedings-article","created":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T02:55:56Z","timestamp":1657940156000},"page":"237-243","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Envy-Free Graph Cutting"],"prefix":"10.24963","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[{"name":"Royal Holloway University of London"}]},{"given":"Eduard","family":"Eiben","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London"}]},{"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Thekla","family":"Hamm","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[{"name":"University of Leeds"}]}],"member":"10584","event":{"number":"31","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2022","name":"Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}","start":{"date-parts":[[2022,7,23]]},"theme":"Artificial Intelligence","location":"Vienna, Austria","end":{"date-parts":[[2022,7,29]]}},"container-title":["Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T11:07:19Z","timestamp":1658142439000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2022\/34"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2022\/34","relation":{},"subject":[],"published":{"date-parts":[[2022,7]]}}}