{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:12:15Z","timestamp":1767856335312,"version":"3.49.0"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T00:00:00Z","timestamp":1672185600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T00:00:00Z","timestamp":1672185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/22"],"award-info":[{"award-number":["NI 369\/22"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/18"],"award-info":[{"award-number":["NI 369\/18"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/21"],"award-info":[{"award-number":["NI 369\/21"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","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":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the NP-hard <jats:sc>Fair Connected Districting<\/jats:sc> problem recently proposed by Stoica et al.\u00a0[AAMAS 2020]: Partition a vertex-colored graph into <jats:italic>k<\/jats:italic>\u00a0connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. <jats:sc>Fair Connected Districting<\/jats:sc> is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for \u201cfair districts\u201d without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. We conduct a fine-grained analysis of the (parameterized) computational complexity of <jats:sc>Fair Connected Districting<\/jats:sc>. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters including treewidth, and problem-specific parameters, including, the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hard, and para-NP-hard).<\/jats:p>","DOI":"10.1007\/s10458-022-09594-2","type":"journal-article","created":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T14:10:15Z","timestamp":1672236615000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A refined complexity analysis of fair districting over graphs"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5102-449X","authenticated-orcid":false,"given":"Niclas","family":"Boehmer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"Koana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,28]]},"reference":[{"key":"9594_CR1","doi-asserted-by":"publisher","first-page":"103576","DOI":"10.1016\/j.artint.2021.103576","volume":"301","author":"A Agarwal","year":"2021","unstructured":"Agarwal, A., Elkind, E., Gan, J., Igarashi, A., Suksompong, W., & Voudouris, A. A. (2021). Schelling games on graphs. Artificial Intelleligence  301, 103576.","journal-title":"Artif. Intell."},{"issue":"4","key":"9594_CR2","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1137\/21M1406854","volume":"19","author":"EA Autry","year":"2021","unstructured":"Autry, E. A., Carter, D., Herschlag, G. J., Hunter, Z., & Mattingly, J. C. (2021). Metropolized multiscale forest recombination for redistricting. Multiscale Modelling Simulation, 19(4), 1885\u20131914.","journal-title":"Multiscale Model. Simul."},{"key":"9594_CR3","unstructured":"Bachrach, Y., Lev, O., Lewenberg, Y., & Zick, Y. (2016). Misrepresentation in district voting. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI \u201916). AAAI Press, (pp. 81\u201387)."},{"key":"9594_CR4","unstructured":"Banerjee, A.V., & Duflo, E. (2011). Poor economics: A radical rethinking of the way to fight global poverty. Public Affairs."},{"key":"9594_CR5","doi-asserted-by":"crossref","unstructured":"Banerjee, A.V., & Pande, R. (2007). Parochial politics: Ethnic preferences and politician corruption.","DOI":"10.2139\/ssrn.976548"},{"key":"9594_CR6","doi-asserted-by":"crossref","unstructured":"Bentert, M., Koana, T., & Niedermeier, R. (2021). The complexity of gerrymandering over graphs: Paths and trees. In: Proceedings of the 47th international workshop on graph-theoretic concepts in computer science (WG \u201921). Springer, (pp. 195\u2013206).","DOI":"10.1007\/978-3-030-86838-3_15"},{"key":"9594_CR7","doi-asserted-by":"crossref","unstructured":"van Bevern\u00a0van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2015). Network-based vertex dissolution. SIAM Journal Discrete Mathematics 29(2), 888\u2013914.","DOI":"10.1137\/140978880"},{"key":"9594_CR8","doi-asserted-by":"crossref","unstructured":"Bhakta, P., Miracle, S., & Randall, D. (2014). Clustering and mixing times for segregation models on $$\\mathbb{z}{}^{{2}}$$. In Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (SODA \u201914). SIAM, (pp. 327\u2013340).","DOI":"10.1137\/1.9781611973402.24"},{"key":"9594_CR9","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Bredereck, R., Knop, D., & Luo, J. (2020). Fine-grained view on bribery for group identification. In Proceedings of the twenty-ninth international joint conference on artificial intelligence (IJCAI \u201920). (pp. 67\u201373). ijcai.org","DOI":"10.24963\/ijcai.2020\/10"},{"key":"9594_CR10","unstructured":"Boehmer, N., & Koana, T. (2022). The complexity of finding fair many-to-one matchings. In Proceedings of the 49th international colloquium on automata, languages, and programming (ICALP \u201922). (pp. 27:1\u201327:18)."},{"key":"9594_CR11","doi-asserted-by":"crossref","unstructured":"Brandt, C., Immorlica, N., Kamath, G., & Kleinberg, R. (2012). An analysis of one-dimensional Schelling segregation. In Proceedings of the 44th symposium on theory of computing conference (STOC \u201912). ACM, (pp. 789\u2013804).","DOI":"10.1145\/2213977.2214048"},{"key":"9594_CR12","doi-asserted-by":"publisher","first-page":"103600","DOI":"10.1016\/j.artint.2021.103600","volume":"302","author":"M Brill","year":"2022","unstructured":"Brill, M., Schmidt-Kraepelin, U., & Suksompong, W. (2022). Margin of victory for tournament solutions. Artificial Intelligence, 302, 103600.","journal-title":"Artificial Intelligence"},{"issue":"4","key":"9594_CR13","doi-asserted-by":"publisher","first-page":"1242","DOI":"10.2307\/2131690","volume":"52","author":"J Campagna","year":"1990","unstructured":"Campagna, J., & Grofman, B. (1990). Party control and partisan bias in 1980s congressional redistricting. The Journal of Politics, 52(4), 1242\u20131257.","journal-title":"The Journal of Politics"},{"issue":"5","key":"9594_CR14","first-page":"223","volume":"60","author":"J Chleb\u00edkov\u00e1","year":"1996","unstructured":"Chleb\u00edkov\u00e1, J. (1996). Approximating the maximally balanced connected partition problem in graphs. Information Processing Lettering, 60(5), 223\u2013230.","journal-title":"Information Processing Lettering"},{"key":"9594_CR15","unstructured":"Cohen-Zemach, A., Lewenberg, Y., & Rosenschein, J. S. (2018). Gerrymandering over graphs. In Proceedings of the 17th international conference on autonomous agents and multiagent systems (AAMAS \u201918). IFAAMAS, (pp. 274\u2013282)."},{"key":"9594_CR16","doi-asserted-by":"crossref","unstructured":"DeFord, D., Duchin, M., & Solomon, J. (2021). Recombination: a family of Markov chains for redistricting. Harvard Data Science Review.","DOI":"10.1162\/99608f92.eb30390f"},{"key":"9594_CR17","unstructured":"Dey, P., & Narahari, Y. (2015). Estimating the margin of victory of an election using sampling. In Proceedings of the twenty-fourth international joint conference on artificial intelligence (IJCAI \u201915). AAAI Press, (pp. 1120\u20131126)."},{"issue":"2","key":"9594_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(85)90008-3","volume":"10","author":"ME Dyer","year":"1985","unstructured":"Dyer, M. E., & Frieze, A. M. (1985). On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10(2), 139\u2013153.","journal-title":"Discrete Applied Mathematics"},{"key":"9594_CR19","unstructured":"EdBuild: Non-white school districts get $23 billion less than white districts, despite serving the same number of students (2019), edbuild.org\/content\/23-billion"},{"key":"9594_CR20","doi-asserted-by":"crossref","unstructured":"Eiben, E., Fomin, F. V., Panolan, F., & Simonov, K. (2020). Manipulating districts to win elections: Fine-grained complexity. In Proceedings of the 34th AAAI conference on artificial intelligence (AAAI \u201920). AAAI Press, (pp. 1902\u20131909).","DOI":"10.1609\/aaai.v34i02.5559"},{"issue":"3","key":"9594_CR21","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1017\/S0003055406062277","volume":"100","author":"EJ Engstrom","year":"2006","unstructured":"Engstrom, E. J. (2006). Stacking the states, stacking the house: the partisan consequences of congressional redistricting in the 19th century. American Political Science Review, 100(3), 419\u2013427.","journal-title":"American Political Science Review"},{"issue":"1","key":"9594_CR22","doi-asserted-by":"publisher","first-page":"313","DOI":"10.7155\/jgaa.00360","volume":"19","author":"D Eppstein","year":"2015","unstructured":"Eppstein, D. (2015). Metric dimension parameterized by max leaf number. Journal of Graph Algorithms Application, 19(1), 313\u2013323.","journal-title":"Journal of Graph Algorithms Application"},{"issue":"4","key":"9594_CR23","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.2307\/1957176","volume":"66","author":"RS Erikson","year":"1972","unstructured":"Erikson, R. S. (1972). Malapportionment, gerrymandering, and party fortunes in congressional elections. American Political Science Review, 66(4), 1234\u20131245.","journal-title":"American Political Science Review"},{"issue":"4","key":"9594_CR24","first-page":"15:1","volume":"2","author":"D Fotakis","year":"2014","unstructured":"Fotakis, D., & Tzamos, C. (2014). On the power of deterministic mechanisms for facility location games. ACM Transaction on Economic and Computation, 2(4), 15:1-15:37.","journal-title":"ACM Transaction on Economic and Computation"},{"key":"9594_CR25","doi-asserted-by":"crossref","unstructured":"Gabow, H. N. (1983). An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the 15th annual ACM symposium on theory of computing (STOC \u201983). ACM, (pp. 448\u2013456).","DOI":"10.1145\/800061.808776"},{"key":"9594_CR26","doi-asserted-by":"crossref","unstructured":"Gupta, S., Jain, P., Panolan, F., Roy, S., & Saurabh, S. (2021). Gerrymandering on graphs: computational complexity and parameterized algorithms. In: Proceedings of the 14th international symposium on algorithmic game theory (SAGT \u201921). Springer, (pp. 140\u2013155).","DOI":"10.1007\/978-3-030-85947-3_10"},{"issue":"2","key":"9594_CR27","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1089\/153312903321578188","volume":"2","author":"S Hirsch","year":"2003","unstructured":"Hirsch, S. (2003). The united states house of unrepresentatives: What went wrong in the latest round of congressional redistricting. Election Law Journal, 2(2), 179\u2013216.","journal-title":"Election Law Journal"},{"key":"9594_CR28","doi-asserted-by":"publisher","first-page":"593","DOI":"10.2307\/1342611","volume":"116","author":"S Issacharoff","year":"2002","unstructured":"Issacharoff, S. (2002). Gerrymandering and political cartels. Harvard Law Review, 116, 593\u2013648.","journal-title":"Harv Law Review"},{"key":"9594_CR29","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.tcs.2021.03.037","volume":"868","author":"T Ito","year":"2021","unstructured":"Ito, T., Kamiyama, N., Kobayashi, Y., & Okamoto, Y. (2021). Algorithms for gerrymandering over graphs. Theoritical Computer Science, 868, 30\u201345.","journal-title":"Theoritical Computer Science"},{"issue":"3","key":"9594_CR30","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"Kannan, R. (1987). Minkowski\u2019s convex body theorem and integer programming. Mathematics of Operation Research, 12(3), 415\u2013440.","journal-title":"Mathematics of Operation Research"},{"issue":"1","key":"9594_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"DJ Kleitman","year":"1991","unstructured":"Kleitman, D. J., & West, D. B. (1991). Spanning trees with many leaves. SIAM Journal on Discrete Mathematics, 4(1), 99\u2013106.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9594_CR32","series-title":"lecture notes in computer science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, computations and approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T. (1994). Treewidth, computations and approximations lecture notes in computer science (Vol. 842). New York: Springer."},{"key":"9594_CR33","unstructured":"Kreisel, L., Boehmer, N., Froese, V., & Niedermeier, R. (2021). Equilibria in schelling games: computational complexity and robustness. In Proceedings of the 21st international conference on autonomous agents and multiagent systems (AAMAS \u201922). IFAAMAS, (pp. 761\u2013769)."},{"issue":"3","key":"9594_CR34","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s00355-008-0336-6","volume":"32","author":"Z Landau","year":"2009","unstructured":"Landau, Z., Reid, O., & Yershov, I. (2009). A fair division solution to the problem of redistricting. Social Choice and Welfare, 32(3), 479\u2013492.","journal-title":"Social Choice and Welfare"},{"key":"9594_CR35","first-page":"17","volume-title":"Fair division and redistricting AMS Special Sessions on The Mathematics of Decisions Elections and Games","author":"Z Landau","year":"2013","unstructured":"Landau, Z., & Su, F. E. (2013). Fair division and redistricting AMS Special Sessions on The Mathematics of Decisions Elections and Games. Rodhe Island: American mathematical society, (pp. 17\u201336)."},{"key":"9594_CR36","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Operation Research, 8, 538\u2013548.","journal-title":"Mathematics of Operation Research"},{"issue":"1","key":"9594_CR37","first-page":"1.10:1","volume":"24","author":"HA Levin","year":"2019","unstructured":"Levin, H. A., & Friedler, S. A. (2019). Automated congressional redistricting. ACM Journal of Experimental Algorithmics, 24(1), 1.10:1-1.10:24.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"9594_CR38","unstructured":"Lewenberg, Y., Lev, O., & Rosenschein, J. S. (2017). Divide and conquer: Using geographic manipulation to win district-based elections. In Proceedings of the 16th conference on autonomous agents and multiagent systems (AAMAS \u201917). ACM, (pp. 624\u2013632)."},{"key":"9594_CR39","doi-asserted-by":"crossref","unstructured":"Lu, P., Sun, X., Wang, Y., & Zhu, Z. A. (2010). Asymptotically optimal strategy-proof mechanisms for two-facility games. In Proceedings of the 11th ACM conference on electronic commerce (EC \u201910). ACM, (pp. 315\u2013324).","DOI":"10.1145\/1807342.1807393"},{"key":"9594_CR40","volume-title":"The Paradox of Representation: Racial Gerrymandering and Minority Interests in Congress","author":"D Lublin","year":"1999","unstructured":"Lublin, D. (1999). The Paradox of Representation: Racial Gerrymandering and Minority Interests in Congress. New Jersey: Princeton University Press."},{"key":"9594_CR41","doi-asserted-by":"crossref","unstructured":"Marx, D. (2007). On the optimality of planar and geometric approximation schemes. In Proceedings of the 48th annual IEEE symposium on foundations of computer science (FOCS 07). (pp. 338\u2013348).","DOI":"10.1109\/FOCS.2007.26"},{"key":"9594_CR42","unstructured":"McCartan, C., Imai, K. (2020). Sequential monte carlo for sampling balanced and compact redistricting plans. CoRR http:\/\/arxiv.org\/2008.06131"},{"key":"9594_CR43","unstructured":"Mitra, A. (2020). Electoral david versus goliath: how does the spatial concentration of electors affect district-based elections? http:\/\/arxiv.org\/2006.11865"},{"issue":"9\u201310","key":"9594_CR44","doi-asserted-by":"publisher","first-page":"1455","DOI":"10.1016\/j.mcm.2008.05.024","volume":"48","author":"C Puppe","year":"2008","unstructured":"Puppe, C., & Tasn\u00e1di, A. (2008). A computational approach to unbiased districting. Mathematical and Computer Modelling, 48(9\u201310), 1455\u20131460.","journal-title":"Mathematical and Computer Modelling"},{"issue":"1","key":"9594_CR45","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.econlet.2009.06.008","volume":"105","author":"C Puppe","year":"2009","unstructured":"Puppe, C., & Tasndi, A. (2009). Optimal redistricting under geographical constraints: Why \"pack and crack\u2019\u2019 does not work. Economics Letters, 105(1), 93\u201396.","journal-title":"Economics Letters"},{"key":"9594_CR46","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the 10th annual ACM symposium on theory of computing (STOC \u201978). ACM, (pp. 216\u2013226).","DOI":"10.1145\/800133.804350"},{"issue":"2","key":"9594_CR47","first-page":"488","volume":"59","author":"TC Schelling","year":"1969","unstructured":"Schelling, T. C. (1969). Models of segregation. American Economic Review, 59(2), 488\u2013493.","journal-title":"American Economic Review"},{"key":"9594_CR48","unstructured":"Stoica, A., Chakraborty, A., Dey, P., & Gummadi, K. P. (2020). Minimizing margin of victory for fair political and educational districting. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS \u201920). IFAAMAS,  (pp. 1305\u20131313)."},{"key":"9594_CR49","doi-asserted-by":"crossref","unstructured":"Xia, L. (2012). Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM conference on electronic commerce (EC \u201912). ACM, (pp. 982\u2013999).","DOI":"10.1145\/2229012.2229086"},{"key":"9594_CR50","doi-asserted-by":"crossref","unstructured":"Zhao, Z., Hettle, C., Gupta, S., Mattingly, J., Randall, D., & Herschlag, G. (2022). Mathematically quantifying gerrymandering and the non-responsiveness of the 2021 Georgia congressional districting plan. In Proceedings of the second ACM conference on equity and access in algorithms, mechanisms, and optimization (EAAMO '\u201922). ACM, (pp. 11\u201315).","DOI":"10.1145\/3551624.3555300"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09594-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09594-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09594-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T07:43:08Z","timestamp":1683790988000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09594-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,28]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9594"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09594-2","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,28]]},"assertion":[{"value":"9 December 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"13"}}