{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T03:47:11Z","timestamp":1782100031971,"version":"3.54.5"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T00:00:00Z","timestamp":1782086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T00:00:00Z","timestamp":1782086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005005","name":"Ben-Gurion University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005005","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2026,12]]},"abstract":"Abstract<\/jats:title>\n \n Fair division<\/jats:italic>\n of resources among competing agents is a fundamental problem in computational social choice and game theory. It has been intensively studied for various types of items (\n divisible<\/jats:italic>\n and\n indivisible<\/jats:italic>\n ) and under various notions of\n fairness<\/jats:italic>\n . We focus on\n Connected Fair Division<\/jats:sc>\n (\n \n $$\\textsf{CFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ), the variant of fair division on graphs, where the\n resources<\/jats:italic>\n are modeled as an\n item graph<\/jats:italic>\n . Here, each agent has to be assigned a connected subgraph of the item graph, and each item has to be assigned to some agent. We introduce a generalization of\n \n $$\\textsf{CFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , termed\n Incomplete<\/jats:sc>\n \n $$\\textsf{CFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n (\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ), where exactly\n p<\/jats:italic>\n vertices of the item graph should be assigned to the agents. This might be useful, in particular when the allocations are intended to be \u201ceconomical\u201d as well as fair. We consider four well-known notions of fairness:\n \n $$\\textsf{PROP}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$\\textsf{EF}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$\\textsf{EF1}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$\\textsf{EFX}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n . First, we prove that\n \n $$\\textsf{EF}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ,\n \n $$\\textsf{EF1}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , and\n \n $$\\textsf{EFX}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n are W[1]-hard parameterized by\n p<\/jats:italic>\n plus the number of agents, even for graphs having constant\n vertex cover number<\/jats:italic>\n (\n \n $$\\textsf{vcn}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ). In contrast, we present a randomized\n \n $$\\textsf{FPT}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n algorithm for\n \n $$\\textsf{PROP}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n -\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n parameterized only by\n p<\/jats:italic>\n . Additionally, we prove both positive and negative results concerning the kernelization complexity of\n \n $$\\textsf{ICFD}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n under all four fairness notions, parameterized by\n p<\/jats:italic>\n ,\n \n $$\\textsf{vcn}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n , and the total number of different valuations in the item graph (\n \n $$\\textsf{val}$$<\/jats:tex-math>\n <\/jats:inline-formula>\n ).\n <\/jats:p>","DOI":"10.1007\/s10458-026-09760-w","type":"journal-article","created":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T02:49:10Z","timestamp":1782096550000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized complexity of incomplete connected fair division"],"prefix":"10.1007","volume":"40","author":[{"given":"Harmender","family":"Gahlawat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,22]]},"reference":[{"key":"9760_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Lewi, K., & Williams, R. (2014). Losing weight by gaining edges. In European Symposium on Algorithms, (pp. 1\u201312). Springer.","DOI":"10.1007\/978-3-662-44777-2_1"},{"issue":"4","key":"9760_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., & Zwick, U. (1995). Color-coding. The Journal of the ACM, 42(4), 844\u2013856. https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"The Journal of the ACM"},{"key":"9760_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Bouveret, S., Caragiannis, I., Giagkousi, I., & Lang, J. (2018). Knowledge, fairness, and social constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, (vol.\u00a032).","DOI":"10.1609\/aaai.v32i1.11590"},{"issue":"1","key":"9760_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10458-021-09532-8","volume":"36","author":"H Aziz","year":"2022","unstructured":"Aziz, H., Caragiannis, I., Igarashi, A., & Walsh, T. (2022). Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(1), 3.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"1","key":"9760_CR5","first-page":"1","volume":"8","author":"Siddharth Barman and Sanath Kumar Krishnamurthy","year":"2020","unstructured":"Siddharth Barman and Sanath Kumar Krishnamurthy. (2020). Approximation algorithms for maximin fair division. ACM Transactions on Economics and Computation (TEAC), 8(1), 1\u201328.","journal-title":"ACM Transactions on Economics and Computation (TEAC)"},{"key":"9760_CR6","doi-asserted-by":"publisher","first-page":"4826","DOI":"10.1609\/aaai.v36i5.20410","volume":"36","author":"B Berger","year":"2022","unstructured":"Berger, B., Cohen, A., Feldman, M., & Fiat, A. (2022). Almost full efx exists for four agents. In Proceedings of the AAAI Conference on Artificial Intelligence, 36, 4826\u20134833.","journal-title":"In Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"9760_CR7","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.geb.2021.11.006","volume":"131","author":"V Bil\u00f2","year":"2022","unstructured":"Bil\u00f2, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C., & Zwicker, W. S. (2022). Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131, 197\u2013221.","journal-title":"Games and Economic Behavior"},{"key":"9760_CR8","unstructured":"Bliem, B., Bredereck, R., & Niedermeier, R. (2016). Complexity of efficient and envy-free resource allocation: Few agents, resources, or utility levels. In IJCAI (pp. 102\u2013108)."},{"key":"9760_CR9","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Bredereck, R., Heeger, K., Knop, D., & Luo, J. (2022). Multivariate algorithmics for eliminating envy by donating goods. In P. Faliszewski, V. Mascardi, C. Pelachaud, & M.\u00a0E. Taylor (eds.), 21st International Conference on Autonomous Agents and Multiagent Systems (pp. 127\u2013135), AAMAS 2022. Auckland, New Zealand, May 9-13, 2022. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). https:\/\/doi.org\/10.5555\/3535850.3535866, https:\/\/www.ifaamas.org\/Proceedings\/aamas2022\/pdfs\/p127.pdf.","DOI":"10.65109\/SNJZ6931"},{"key":"9760_CR10","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., & Peters, D. (2017). Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (pp. 135\u2013141), IJCAI\u201917. AAAI Press.","DOI":"10.24963\/ijcai.2017\/20"},{"issue":"2","key":"9760_CR11","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10458-015-9287-3","volume":"30","author":"S Bouveret","year":"2016","unstructured":"Bouveret, S., & Lema\u00eetre, M. (2016). Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, 30(2), 259\u2013290.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"2","key":"9760_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1023\/B:THEO.0000024421.85722.0a","volume":"55","author":"SJ Brams","year":"2003","unstructured":"Brams, S. J., Edelman, P. H., & Fishburn, P. C. (2003). Fair division of indivisible items. Theory and Decision, 55(2), 147\u2013180.","journal-title":"Theory and Decision"},{"key":"9760_CR13","doi-asserted-by":"crossref","unstructured":"Brams, S. J., & Taylor, A.\u00a0D. (1996). Fair Division: From cake-cutting to dispute resolution. Cambridge University Press.","DOI":"10.1017\/CBO9780511598975"},{"issue":"6","key":"9760_CR14","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1086\/664613","volume":"119","author":"E Budish","year":"2011","unstructured":"Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061\u20131103.","journal-title":"Journal of Political Economy"},{"key":"9760_CR15","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Gravin, N., & Huang, X. (2019). Envy-freeness up to any item with high nash welfare: The virtue of donating items. In Proceedings of the 2019 ACM Conference on Economics and Computation, (pp. 527\u2013545).","DOI":"10.1145\/3328526.3329574"},{"issue":"3","key":"9760_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3355902","volume":"7","author":"I Caragiannis","year":"2019","unstructured":"Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3), 1\u201332.","journal-title":"ACM Transactions on Economics and Computation (TEAC)"},{"key":"9760_CR17","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Micha, E., & Shah, N. (2022). A little charity guarantees fair connected graph partitioning. In Proceedings of the AAAI Conference on Artificial Intelligence (vol. 36, pp. 4908\u20134916).","DOI":"10.1609\/aaai.v36i5.20420"},{"key":"9760_CR18","doi-asserted-by":"crossref","unstructured":"Chaudhury, B.\u00a0R., Garg, J., & Mehlhorn, K. (2020). Efx exists for three agents. In Proceedings of the 21st ACM Conference on Economics and Computation (pp. 1\u201319).","DOI":"10.1145\/3391403.3399511"},{"issue":"4","key":"9760_CR19","doi-asserted-by":"publisher","first-page":"1336","DOI":"10.1137\/20M1359134","volume":"50","author":"BR Chaudhury","year":"2021","unstructured":"Chaudhury, B. R., Kavitha, T., Mehlhorn, K., & Sgouritsa, A. (2021). A little charity guarantees almost envy-freeness. SIAM Journal on Computing, 50(4), 1336\u20131358.","journal-title":"SIAM Journal on Computing"},{"key":"9760_CR20","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms, vol.\u00a05. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9760_CR21","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Ganian, R., Hamm, T., & Sebastian Ordyniak. (2021). The parameterized complexity of connected fair division. In IJCAI (pp. 139\u2013145).","DOI":"10.24963\/ijcai.2021\/20"},{"key":"9760_CR22","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2022). The complexity of envy-free graph cutting. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI) (pp 237\u2013243).","DOI":"10.24963\/ijcai.2022\/34"},{"key":"9760_CR23","volume-title":"Graph theory","author":"R Diestel","year":"2018","unstructured":"Diestel, R. (2018). Graph theory. Incorporated: Springer Publishing Company."},{"key":"9760_CR24","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S. (2009). Incompressibility through colors and ids. In International Colloquium on Automata, Languages, and Programming (pp. 378\u2013389). Springer.","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"9760_CR25","doi-asserted-by":"crossref","unstructured":"Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2023). (vol. 315, pp. 103826). Elsevier.","DOI":"10.1016\/j.artint.2022.103826"},{"key":"9760_CR26","doi-asserted-by":"publisher","unstructured":"Fellows, M.\u00a0R. (2006). The lost continent of polynomial time: Preprocessing and kernelization. IWPEC\u201906 (pp. 276\u2013277), Berlin, Heidelberg. Springer-Verlag. https:\/\/doi.org\/10.1007\/11847250_25.","DOI":"10.1007\/11847250_25"},{"key":"9760_CR27","doi-asserted-by":"crossref","unstructured":"Fomin, F.\u00a0V., Lokshtanov, D., Saurabh, S., & Zehavi, M. (2019). Kernelization: theory of parameterized preprocessing. Cambridge University Press.","DOI":"10.1017\/9781107415157"},{"key":"9760_CR28","unstructured":"Gahlawat, H., & Zehavi, M. (2023). Parameterized complexity of incomplete connected fair division. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik."},{"issue":"14","key":"9760_CR29","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1016\/j.artint.2009.06.005","volume":"173","author":"Y Gao","year":"2009","unstructured":"Gao, Y. (2009). Data reductions, fixed parameter tractability, and random weighted d-cnf satisfiability. Artificial Intelligence, 173(14), 1343\u20131366.","journal-title":"Artificial Intelligence"},{"key":"9760_CR30","doi-asserted-by":"crossref","unstructured":"Greco, G., & Scarcello, F. (2020). The complexity of computing maximin share allocations on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, (vol. 34, pp. 2006\u20132013).","DOI":"10.1609\/aaai.v34i02.5572"},{"key":"9760_CR31","doi-asserted-by":"crossref","unstructured":"Greco, G., & Scarcello, F. (2024). Maxileximin envy allocations and connected goods. In Proceedings of the AAAI Conference on Artificial Intelligence, (vol. 38, pp. 9713\u20139721).","DOI":"10.1609\/aaai.v38i9.28829"},{"issue":"1","key":"9760_CR32","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., & Niedermeier, R. (2007). Invitation to data reduction and problem kernelization. ACM SIGACT News, 38(1), 31\u201345.","journal-title":"ACM SIGACT News"},{"key":"9760_CR33","doi-asserted-by":"crossref","unstructured":"Igarashi, A. (2023). How to cut a discrete cake fairly. In Proceedings of the AAAI Conference on Artificial Intelligence, (vol. 37, pp. 5681\u20135688).","DOI":"10.1609\/aaai.v37i5.25705"},{"key":"9760_CR34","doi-asserted-by":"crossref","unstructured":"Igarashi, A., & Peters, D. (2019). Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the AAAI conference on artificial intelligence, (vol. 33, pp. 2045\u20132052).","DOI":"10.1609\/aaai.v33i01.33012045"},{"issue":"2","key":"9760_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3140756","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A. D., & Wang, J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM), 65(2), 1\u201327.","journal-title":"Journal of the ACM (JACM)"},{"key":"9760_CR36","doi-asserted-by":"crossref","unstructured":"Lipton, R.\u00a0J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, (pp. 125\u2013131).","DOI":"10.1145\/988772.988792"},{"key":"9760_CR37","doi-asserted-by":"crossref","unstructured":"Lonc, Z. (2023). Approximating fair division on d-claw-free graphs. In IJCAI (pp. 2826\u20132834).","DOI":"10.24963\/ijcai.2023\/315"},{"key":"9760_CR38","doi-asserted-by":"crossref","unstructured":"Madathil, J. (2023). Fair division of a graph into compact bundles. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2835\u20132843).","DOI":"10.24963\/ijcai.2023\/316"},{"key":"9760_CR39","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.\u00a0J., & Srinivasan, A. (1995). Splitters and near-optimal derandomization. In Proceedings of IEEE 36th Annual Foundations of Computer Science (pp. 182\u2013191). IEEE.","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"3\u20134","key":"9760_CR40","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R Niedermeier","year":"2000","unstructured":"Niedermeier, R., & Rossmanith, P. (2000). A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters, 73(3\u20134), 125\u2013129.","journal-title":"Information Processing Letters"},{"issue":"2","key":"9760_CR41","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/19M124397X","volume":"34","author":"B Plaut","year":"2020","unstructured":"Plaut, B., & Roughgarden, T. (2020). Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2), 1039\u20131068.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"9760_CR42","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1111\/j.1468-2354.2009.00572.x","volume":"51","author":"T S\u00f6nmez","year":"2010","unstructured":"S\u00f6nmez, T., & \u00dcnver, M. U. (2010). Course bidding at business schools. International Economic Review, 51(1), 99\u2013123.","journal-title":"International Economic Review"},{"key":"9760_CR43","first-page":"1","volume-title":"Covering trains by stations or the power of data reduction","author":"K Weihe","year":"1998","unstructured":"Weihe, K. (1998). Covering trains by stations or the power of data reduction (pp. 1\u20138). ALEX: Proceedings of Algorithms and Experiments."},{"key":"9760_CR44","doi-asserted-by":"crossref","unstructured":"Williamson, D.\u00a0P., & Shmoys, D.\u00a0B. (2011). The design of approximation algorithms. Cambridge university press.","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-026-09760-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-026-09760-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-026-09760-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T02:49:40Z","timestamp":1782096580000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-026-09760-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,22]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["9760"],"URL":"https:\/\/doi.org\/10.1007\/s10458-026-09760-w","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,22]]},"assertion":[{"value":"20 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"34"}}