{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:27:29Z","timestamp":1764350849543,"version":"3.37.3"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T00:00:00Z","timestamp":1688083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T00:00:00Z","timestamp":1688083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62172446"],"award-info":[{"award-number":["62172446"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Open Project of Xiangjiang Laboratory","award":["22XJ02002","22XJ03005"],"award-info":[{"award-number":["22XJ02002","22XJ03005"]}]},{"DOI":"10.13039\/501100005690","name":"Universit\u00e4t des Saarlandes","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005690","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,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the parameterized complexity of winner determination problems for three prevalent <jats:italic>k<\/jats:italic>-committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin\u2013Courant\u2019s approval voting (CCAV). It is known that these problems are computationally hard. Although they have been studied from the parameterized complexity point of view with respect to several natural parameters, many of them turned out to be -hard or -hard. Aiming at obtaining plentiful fixed-parameter algorithms, we revisit these problems by considering more natural single parameters, combined parameters, and structural parameters.<\/jats:p>","DOI":"10.1007\/s10458-023-09610-z","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T10:02:35Z","timestamp":1688119355000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7731-6818","authenticated-orcid":false,"given":"Yongjie","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,30]]},"reference":[{"key":"9610_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Choudhary, P., Jain, P., Kanesh, L., Sahlot, V., & Saurabh, S. (2018). Hitting and covering partially. In COCOON (pp. 751\u2013763).","DOI":"10.1007\/978-3-319-94776-1_62"},{"issue":"2","key":"9610_CR2","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/s00355-016-1019-3","volume":"48","author":"H Aziz","year":"2017","unstructured":"Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., & Walsh, T. (2017). Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2), 461\u2013485.","journal-title":"Social Choice and Welfare"},{"key":"9610_CR3","unstructured":"Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., & Walsh, T. (2015). Computational aspects of multi-winner approval voting. In AAMAS (pp. 107\u2013115)."},{"key":"9610_CR4","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1613\/jair.3896","volume":"47","author":"N Betzler","year":"2013","unstructured":"Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47, 475\u2013519.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"6","key":"9610_CR5","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0020-0190(02)00434-9","volume":"85","author":"M Bl\u00e4ser","year":"2003","unstructured":"Bl\u00e4ser, M. (2003). Computing small partial coverings. Information Processing Letters, 85(6), 327\u2013331.","journal-title":"Information Processing Letters"},{"key":"9610_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. L. (2012). Fixed-parameter tractability of treewidth and pathwidth. In The Multivariate Algorithmic Revolution and Beyond (pp. 196\u2013227).","DOI":"10.1007\/978-3-642-30891-8_12"},{"issue":"1\u20132","key":"9610_CR7","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H. L. (1993). A tourist guide through treewidth. Acta Cybernetica, 11(1\u20132), 1\u201321.","journal-title":"Acta Cybernetica"},{"issue":"2","key":"9610_CR8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H. L., Drange, P. G., Dregi, M. S., Fomin, F. V., Lokshtanov, D., & Pilipczuk, M. (2016). A $$c^k n$$ 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2), 317\u2013378.","journal-title":"SIAM Journal on Computing"},{"key":"9610_CR9","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. L., & Kloks, T. (1991). Better algorithms for the pathwidth and treewidth of graphs. In ICALP (pp. 544\u2013555).","DOI":"10.1007\/3-540-54233-7_162"},{"key":"9610_CR10","unstructured":"Boehmer, N., & Schaar, N. (2023). Collecting, classifying, analyzing, and using real-world ranking data. In AAMAS (pp. 1706\u20131715)."},{"issue":"3\u20134","key":"9610_CR11","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s11127-007-9165-x","volume":"132","author":"SJ Brams","year":"2007","unstructured":"Brams, S. J., Kilgour, D. M., & Sanver, M. R. (2007). A minimax procedure for electing committees. Public Choice, 132(3\u20134), 401\u2013420.","journal-title":"Public Choice"},{"key":"9610_CR12","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V. B., & Spinrad, J. P. (1999). Graph classes: A survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia.","DOI":"10.1137\/1.9780898719796"},{"key":"9610_CR13","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Knop, D., & Niedermeier, R. (2021). Parameterized algorithms for finding a collective set of items. In AAAI (pp. 1838\u20131845).","DOI":"10.1609\/aaai.v34i02.5551"},{"key":"9610_CR14","doi-asserted-by":"crossref","first-page":"103403","DOI":"10.1016\/j.artint.2020.103403","volume":"290","author":"R Bredereck","year":"2021","unstructured":"Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R., Skowron, P., & Talmon, N. (2021). Robustness among multiwinner voting rules. Artificial Intelligence, 290, 103403.","journal-title":"Artificial Intelligence"},{"key":"9610_CR15","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/j.tcs.2020.01.017","volume":"814","author":"R Bredereck","year":"2020","unstructured":"Bredereck, R., Faliszewski, P., Niedermeier, R., Skowron, P., & Talmon, N. (2020). Mixed integer programming with convex\/concave constraints: Fixed-parameter tractability and applications to multicovering and voting. Theoretical Computer Science, 814, 86\u2013105.","journal-title":"Theoretical Computer Science"},{"key":"9610_CR16","doi-asserted-by":"crossref","unstructured":"Byrka, J., & Sornat, K. (2014). PTAS for minimax approval voting. In WINE (pp. 203\u2013217).","DOI":"10.1007\/978-3-319-13129-0_15"},{"issue":"1","key":"9610_CR17","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L Cai","year":"2008","unstructured":"Cai, L. (2008). Parameterized complexity of cardinality constrained optimization problems. The Computer Journal, 51(1), 102\u2013121.","journal-title":"The Computer Journal"},{"issue":"3","key":"9610_CR18","doi-asserted-by":"crossref","first-page":"718","DOI":"10.2307\/1957270","volume":"77","author":"JR Chamberlin","year":"1983","unstructured":"Chamberlin, J. R., & Courant, P. N. (1983). Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3), 718\u2013733.","journal-title":"American Political Science Review"},{"key":"9610_CR19","unstructured":"Clearwater, A., Puppe, C., & Slinko, A. (2015). Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In IJCAI (pp. 32\u201338)."},{"key":"9610_CR20","unstructured":"Cornaz, D., Galand, L., & Spanjaard, O. (2012). Bounded single-peaked width and proportional representation. In ECAI (pp. 270\u2013275)."},{"issue":"1\u20132","key":"9610_CR21","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., & Mosbah, M. (1993). Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1\u20132), 49\u201382.","journal-title":"Theoretical Computer Science"},{"key":"9610_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Springer."},{"key":"9610_CR23","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1613\/jair.1.11253","volume":"63","author":"M Cygan","year":"2018","unstructured":"Cygan, M., Kowalik, L., Socala, A., & Sornat, K. (2018). Approximation and parameterized complexity of minimax approval voting. Journal of Artificial Intelligence Research, 63, 495\u2013513.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"9610_CR24","first-page":"13","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., & Saurabh, S. (2014). Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 11(2), 13.","journal-title":"ACM Transactions on Algorithms"},{"key":"9610_CR25","doi-asserted-by":"crossref","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Texts in computer science. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1\u20132","key":"9610_CR26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R. G., & Fellows, M. R. (1995). Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1\u20132), 109\u2013131.","journal-title":"Theoretical Computer Science"},{"key":"9610_CR27","unstructured":"Downey, R. G., & Fellows, M. R. (1992). Fixed parameter tractability and completeness. In Complexity Theory: Current Research (pp. 191\u2013225)."},{"issue":"3","key":"9610_CR28","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s00355-017-1026-z","volume":"48","author":"E Elkind","year":"2017","unstructured":"Elkind, E., Faliszewski, P., Skowron, P., & Slinko, A. (2017). Properties of multiwinner voting rules. Social Choice and Welfare, 48(3), 599\u2013632.","journal-title":"Social Choice and Welfare"},{"key":"9610_CR29","unstructured":"Elkind, E., & Lackner, M. (2015). Structure in dichotomous preferences. In IJCAI (pp. 2019\u20132025)."},{"key":"9610_CR30","doi-asserted-by":"crossref","unstructured":"Elkind, E., & Lackner, M. (2014). On detecting nearly structured preference profiles. In AAAI (pp. 661\u2013667).","DOI":"10.1609\/aaai.v28i1.8823"},{"volume-title":"Trends in computational social choice","year":"2017","key":"9610_CR31","unstructured":"Endriss, U. (Ed.). (2017). Trends in computational social choice. AI Access."},{"issue":"3","key":"9610_CR32","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s00355-018-1126-4","volume":"51","author":"P Faliszewski","year":"2018","unstructured":"Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2018). Multiwinner analogues of the plurality rule: Axiomatic and algorithmic perspectives. Social Choice and Welfare, 51(3), 513\u2013550.","journal-title":"Social Choice and Welfare"},{"key":"9610_CR33","unstructured":"Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2016). Committee scoring rules: Axiomatic classification and hierarchy. In IJCAI (pp. 250\u2013256)."},{"key":"9610_CR34","unstructured":"Faliszewski, P., Skowron, P., & Talmon, N. (2017). Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules. In AAMAS (pp. 6\u201314)."},{"issue":"5","key":"9610_CR35","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1007\/s10732-018-9376-y","volume":"24","author":"P Faliszewski","year":"2018","unstructured":"Faliszewski, P., Slinko, A., Stahl, K., & Talmon, N. (2018). Achieving fully proportional representation by clustering voters. Journal of Heuristics, 24(5), 725\u2013756.","journal-title":"Journal of Heuristics"},{"issue":"4","key":"9610_CR36","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1109\/TST.2014.6867519","volume":"19","author":"H Fernau","year":"2014","unstructured":"Fernau, H., Fomin, F. V., Lokshtanov, D., Mnich, M., Philip, G., & Saurabh, S. (2014). Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. Tsinghua Science and Technology, 19(4), 374\u2013386.","journal-title":"Tsinghua Science and Technology"},{"issue":"4","key":"9610_CR37","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.1007\/s00453-017-0297-1","volume":"80","author":"FV Fomin","year":"2018","unstructured":"Fomin, F. V., Liedloff, M., Montealegre, P., & Todinca, I. (2018). Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica, 80(4), 1146\u20131169.","journal-title":"Algorithmica"},{"issue":"3","key":"9610_CR38","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"9610_CR39","doi-asserted-by":"crossref","unstructured":"Gawron, G., & Faliszewski. P. (2022). Using multiwinner voting to search for movies. In EUMAS (pp. 134\u2013151).","DOI":"10.1007\/978-3-031-20614-6_8"},{"key":"9610_CR40","doi-asserted-by":"crossref","unstructured":"Ghosh, S., Mundhe, M., Hernandez, K., & Sen, S. (1999). Voting for movies: The anatomy of a recommender system. In AGENTS (pp. 434\u2013435).","DOI":"10.1145\/301136.301303"},{"key":"9610_CR41","doi-asserted-by":"crossref","unstructured":"Guo, J., Niedermeier, R., & Wernicke, S. (2005). Parameterized complexity of generalized vertex cover problems. In WADS (pp. 36\u201348).","DOI":"10.1007\/11534273_5"},{"key":"9610_CR42","doi-asserted-by":"crossref","unstructured":"Gupta, S., Jain, P., Saurabh, S., & Talmon, N. (2021). Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules. In IJCAI (pp. 217\u2013223).","DOI":"10.24963\/ijcai.2021\/31"},{"key":"9610_CR43","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-3-642-02839-7_6","volume-title":"Handbook on Approval Voting","author":"DM Kilgour","year":"2010","unstructured":"Kilgour, D. M. (2010). Approval balloting for multi-winner elections. In J.-F. Laslier & M. R. Sanver (Eds.), Handbook on Approval Voting (pp. 105\u2013124). Springer."},{"key":"9610_CR44","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/978-3-642-20441-8_12","volume-title":"Electoral systems-paradoxes, assumptions, and procedures","author":"DM Kilgour","year":"2012","unstructured":"Kilgour, D. M., & Marshall, E. (2012). Approval balloting for fixed-size committees. In D. S. Felsenthal & M. Machover (Eds.), Electoral systems-paradoxes, assumptions, and procedures (pp. 305\u2013326). Springer."},{"key":"9610_CR45","doi-asserted-by":"crossref","unstructured":"Kloks, T. (eds.) (1994). Treewidth: Computations and approximations. Lecture Notes in Computer Science, vol. 842. Springer.","DOI":"10.1007\/BFb0045375"},{"issue":"2","key":"9610_CR46","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T Kloks","year":"1995","unstructured":"Kloks, T., & Kratsch, D. (1995). Treewidth of chordal bipartite graphs. Journal of Algorithms, 19(2), 266\u2013281.","journal-title":"Journal of Algorithms"},{"key":"9610_CR47","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.dam.2019.01.027","volume":"278","author":"PK Krause","year":"2020","unstructured":"Krause, P. K., Larisch, L., & Salfelder, F. (2020). The tree-width of C. Discrete Applied Mathematics, 278, 136\u2013152.","journal-title":"Discrete Applied Mathematics"},{"key":"9610_CR48","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-09016-5","volume-title":"Multi-winner voting with approval preferences","author":"M Lackner","year":"2023","unstructured":"Lackner, M., & Skowron, P. (2023). Multi-winner voting with approval preferences. Springer."},{"key":"9610_CR49","doi-asserted-by":"crossref","DOI":"10.1016\/j.jet.2020.105173","volume":"192","author":"M Lackner","year":"2021","unstructured":"Lackner, M., & Skowron, P. (2021). Consistent approval-based multi-winner rules. Journal of Economic Theory, 192, 105173.","journal-title":"Journal of Economic Theory"},{"key":"9610_CR50","unstructured":"LeGrand, R. (2004). Analysis of the minimax procedure. Techical Report, Department of Computer Science and Engineering, Washington University, St. Louis, USA"},{"issue":"4","key":"9610_CR51","doi-asserted-by":"crossref","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 Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematics of Operations Research"},{"key":"9610_CR52","unstructured":"Lin, A.P. (2011). The complexity of manipulating $$k$$-approval elections. In ICAART (Vol. 2, pp. 212\u2013218). arXiv:1005.4159."},{"key":"9610_CR53","unstructured":"Liu, H., & Guo, J. (2016). Parameterized complexity of winner determination in minimax committee elections. In AAMAS (pp. 341\u2013349)."},{"key":"9610_CR54","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., & Plummer, M. D. (1986). Matching theory. Elsevier."},{"key":"9610_CR55","unstructured":"Maniu, S., Senellart, P., & Jog, S. (2019). An experimental study of the treewidth of real-world graph data. In ICDT (p. 12)."},{"issue":"1","key":"9610_CR56","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/s13015-022-00213-z","volume":"17","author":"B Marchand","year":"2022","unstructured":"Marchand, B., Ponty, Y., & Bulteau, L. (2022). Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics. Algorithms for Molecular Biology, 17(1), 8.","journal-title":"Algorithms for Molecular Biology"},{"key":"9610_CR57","unstructured":"Misra, N., Nabeel, A., & Singh, H. (2015). On the parameterized complexity of minimax approval voting. In: AAMAS (pp. 97\u2013105)."},{"key":"9610_CR58","doi-asserted-by":"crossref","unstructured":"Peters, D. (2018). Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections. In AAAI (pp. 1169\u20131176).","DOI":"10.1609\/aaai.v32i1.11460"},{"key":"9610_CR59","doi-asserted-by":"crossref","unstructured":"Peters, D., & Elkind, E. (2016). Preferences single-peaked on nice trees. In AAAI (pp. 594\u2013600).","DOI":"10.1609\/aaai.v30i1.10049"},{"key":"9610_CR60","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1613\/jair.1.11732","volume":"68","author":"D Peters","year":"2020","unstructured":"Peters, D., & Lackner, M. (2020). Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 68, 463\u2013502.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3","key":"9610_CR61","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s00355-007-0235-2","volume":"30","author":"AD Procaccia","year":"2008","unstructured":"Procaccia, A. D., Rosenschein, J. S., & Zohar, A. (2008). On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3), 353\u2013362.","journal-title":"Social Choice and Welfare"},{"key":"9610_CR62","unstructured":"Procaccia, A.D., Rosenschein, J.S., & Zohar, A. (2007). Multi-winner elections: Complexity of manipulation, control and winner-determination. In IJCAI (pp. 1476\u20131481)."},{"issue":"3","key":"9610_CR63","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309\u2013322.","journal-title":"Journal of algorithms"},{"key":"9610_CR64","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of linear and integer programming. Wiley."},{"key":"9610_CR65","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.ic.2017.10.002","volume":"257","author":"P Skowron","year":"2017","unstructured":"Skowron, P. (2017). FPT approximation schemes for maximizing submodular functions. Information and Computation, 257, 65\u201378.","journal-title":"Information and Computation"},{"key":"9610_CR66","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1613\/jair.5628","volume":"60","author":"P Skowron","year":"2017","unstructured":"Skowron, P., & Faliszewski, P. (2017). Chamberlin-Courant rule with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. Journal of Artificial Intelligence Research, 60, 687\u2013716.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9610_CR67","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.artint.2016.09.003","volume":"241","author":"P Skowron","year":"2016","unstructured":"Skowron, P., Faliszewski, P., & Lang, J. (2016). Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241, 191\u2013216.","journal-title":"Artificial Intelligence"},{"key":"9610_CR68","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.tcs.2014.12.012","volume":"569","author":"P Skowron","year":"2015","unstructured":"Skowron, P., Yu, L., Faliszewski, P., & Elkind, E. (2015). The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 569, 43\u201357.","journal-title":"Theoretical Computer Science"},{"key":"9610_CR69","unstructured":"Sui, X., Francois-Nienaber, A., & Boutilier, C. (2013). Multi-dimensional single-peaked consistency and its approximations. In IJCAI (pp. 375\u2013382)."},{"key":"9610_CR70","unstructured":"Thiele, T. N. (1895). Om Flerfoldsvalg. In: Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger (pp. 415\u2013441)."},{"issue":"2","key":"9610_CR71","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M. (1998). All structured programs have small tree-width and good register allocation. Information and Computation, 142(2), 159\u2013181.","journal-title":"Information and Computation"},{"key":"9610_CR72","unstructured":"van\u00a0der Zanden, T. C. (2019). Theory and practical applications of treewidth. Ph.D. thesis, Utrecht University, Netherlands."},{"key":"9610_CR73","volume-title":"Introduction to graph theory","author":"DB West","year":"2000","unstructured":"West, D. B. (2000). Introduction to graph theory. Prentice-Hall."},{"key":"9610_CR74","first-page":"376","volume":"14","author":"A Yamaguchi","year":"2003","unstructured":"Yamaguchi, A., Aoki, K. F., & Mamitsuka, H. (2003). Graph complexity of chemical compounds in biological pathways. Genome Informatics, 14, 376\u2013377.","journal-title":"Genome Informatics"},{"key":"9610_CR75","doi-asserted-by":"crossref","unstructured":"Yang, Y. (2021). A model of winners allocation. In: AAAI (pp. 5760\u20135767).","DOI":"10.1609\/aaai.v35i6.16722"},{"key":"9610_CR76","unstructured":"Yang, Y. (2020). On the complexity of destructive bribery in approval-based multi-winner voting. In AAMAS (pp. 1584\u20131592)."},{"key":"9610_CR77","doi-asserted-by":"crossref","unstructured":"Yang, Y. (2019). Complexity of manipulating and controlling approval-based multiwinner voting. In IJCAI (pp. 637\u2013643).","DOI":"10.24963\/ijcai.2019\/90"},{"key":"9610_CR78","doi-asserted-by":"crossref","unstructured":"Yang, Y. (2019). On the tree representations of dichotomous preferences. In IJCAI (pp. 644\u2013650).","DOI":"10.24963\/ijcai.2019\/91"},{"key":"9610_CR79","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/j.jcss.2017.06.004","volume":"89","author":"Y Yang","year":"2017","unstructured":"Yang, Y., & Guo, J. (2017). The control complexity of $$r$$-approval: From the single-peaked case to the general case. Journal of Computer and System Sciences, 89, 432\u2013449.","journal-title":"Journal of Computer and System Sciences"},{"key":"9610_CR80","unstructured":"Yang, Y., & Wang, J. (2018). Parameterized complexity of multi-winner determination: More effort towards fixed-parameter tractability. In AAMAS (pp. 2142\u20132144)."},{"key":"9610_CR81","unstructured":"Yu, L., Chan, H., & Elkind, E. (2013). Multiwinner elections under preferences that are single-peaked on a tree. In IJCAI (pp. 425\u2013431)."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-023-09610-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-023-09610-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-023-09610-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T04:51:43Z","timestamp":1702875103000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-023-09610-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,30]]},"references-count":81,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9610"],"URL":"https:\/\/doi.org\/10.1007\/s10458-023-09610-z","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2023,6,30]]},"assertion":[{"value":"26 May 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"28"}}