{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T16:41:02Z","timestamp":1775752862392,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T00:00:00Z","timestamp":1705881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider GROUP CONTROL BY ADDING INDIVIDUALS (GCAI) in the setting of group identification for two procedural rules\u2014the consensus-start-respecting rule and the liberal-start-respecting rule. It is known that GCAI for both rules are NP-hard, but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained open. We resolve both open problems in the affirmative. In addition, we strengthen the NP-hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are W[2]-hard. Notably, the W[2]-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem becomes polynomial-time solvable in this special case. We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable. Our reductions for showing W[2]-hardness also imply several algorithmic lower bounds.<\/jats:p>","DOI":"10.1007\/s11704-023-2700-1","type":"journal-article","created":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T13:02:53Z","timestamp":1705928573000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Group control for procedural rules: parameterized complexity and consecutive domains"],"prefix":"10.1007","volume":"18","author":[{"given":"Yongjie","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dinko","family":"Dimitrov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,22]]},"reference":[{"issue":"160","key":"2700_CR1","first-page":"385","volume":"40","author":"A Kasher","year":"1997","unstructured":"Kasher A, Rubinstein A. On the question \u201cWho is a J?\u201d: a social choice approach. Logique et Analyse, 1997, 40(160): 385\u2013395","journal-title":"Logique et Analyse"},{"key":"2700_CR2","unstructured":"Kasher A. Jewish collective identity. In: Goldberg D T, Krausz M, eds. Jewish Identity. Temple University Press, 1993, 56\u201378"},{"key":"2700_CR3","first-page":"123v134","volume-title":"Consensual Processes","author":"D Dimitrov","year":"2011","unstructured":"Dimitrov D. The social choice approach to group identification. In: Herrera-Viedma E, Garc\u00eda-Lapresta J L, Kacprzyk J, Fedrizzi M, Nurmi H, Zadro\u017cny S, eds. Consensual Processes. Berlin: Springer, 2011, 123v134"},{"issue":"2","key":"2700_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.mathsocsci.2007.06.001","volume":"54","author":"D Dimitrov","year":"2007","unstructured":"Dimitrov D, Sung S C, Xu Y. Procedural group identification. Mathematical Social Sciences, 2007, 54(2): 137\u2013146","journal-title":"Mathematical Social Sciences"},{"issue":"1","key":"2700_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.mathsocsci.2007.04.005","volume":"54","author":"H Nicolas","year":"2007","unstructured":"Nicolas H. \u201cI want to be a J!\u201d: Liberalism in group identification problems. Mathematical Social Sciences, 2007, 54(1): 59\u201370","journal-title":"Mathematical Social Sciences"},{"issue":"1","key":"2700_CR6","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.geb.2007.08.006","volume":"63","author":"A D Miller","year":"2008","unstructured":"Miller A D. Group identification. Games and Economic Behavior, 2008, 63(1): 188\u2013202","journal-title":"Games and Economic Behavior"},{"issue":"2","key":"2700_CR7","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0022-0531(03)00080-2","volume":"110","author":"D Samet","year":"2003","unstructured":"Samet D, Schmeidler D. Between liberalism and democracy. Journal of Economic Theory, 2003, 110(2): 213\u2013233","journal-title":"Journal of Economic Theory"},{"issue":"8\u20139","key":"2700_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0895-7177(92)90085-Y","volume":"16","author":"J J Bartholdi","year":"1992","unstructured":"Bartholdi J J, Tovey C A, Trick M A. How hard is it to control an election? Mathematical and Computer Modelling, 1992, 16(8\u20139): 27\u201340","journal-title":"Mathematical and Computer Modelling"},{"issue":"5","key":"2700_CR9","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/s10458-018-9392-1","volume":"32","author":"Y Yang","year":"2018","unstructured":"Yang Y, Dimitrov D. How hard is it to control a group? Autonomous Agents and Multi-Agent Systems, 2018, 32(5): 672\u2013692","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"1","key":"2700_CR10","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/s10458-019-09427-9","volume":"34","author":"G Erd\u00e9lyi","year":"2020","unstructured":"Erd\u00e9lyi G, Reger C, Yang Y. The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems, 2020, 34(1): 8","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"2700_CR11","doi-asserted-by":"crossref","unstructured":"Erd\u00e9lyi G, Reger C, Yang Y. Complexity of group identification with partial information. In: Proceedings of the 5th International Conference on Algorithmic Decision Theory. 2017, 182\u2013196","DOI":"10.1007\/978-3-319-67504-6_13"},{"key":"2700_CR12","unstructured":"Erd\u00e9lyi G, Yang Y. Microbribery in group identification. In: Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems. 2020, 1840\u20131842"},{"key":"2700_CR13","doi-asserted-by":"crossref","unstructured":"Boehmer N, Bredereck R, Knop D, Luo J. Fine-grained view on bribery for group identification. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence. 2020, 67\u201373","DOI":"10.24963\/ijcai.2020\/10"},{"key":"2700_CR14","unstructured":"Junker E. Broadening the complexity-theoretic analysis of manipulative attacks in group identification. Humboldt Universitat zu Berlin, Dissertation, 2022"},{"key":"2700_CR15","unstructured":"Junker E. Manipulative attacks and group identification. 2022, arXiv preprint arXiv: 2203.16151"},{"key":"2700_CR16","unstructured":"Bla\u017eej V. Complexity of games on graphs. Czech Technical University, Dissertation, 2022"},{"key":"2700_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.mathsocsci.2022.11.003","volume":"121","author":"Y Yang","year":"2023","unstructured":"Yang Y, Dimitrov D. Group control for consent rules with consecutive qualifications. Mathematical Social Sciences, 2023, 121: 1\u20137","journal-title":"Mathematical Social Sciences"},{"key":"2700_CR18","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1613\/jair.4647","volume":"53","author":"F Brandt","year":"2015","unstructured":"Brandt F, Brill M, Hemaspaandra E, Hemaspaandra L A. Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 2015, 53: 439\u2013496","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"2700_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.ic.2010.09.001","volume":"209","author":"P Faliszewski","year":"2011","unstructured":"Faliszewski P, Hemaspaandra E, Hemaspaandra L A, Rothe J. The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 2011, 209(2): 89\u2013107","journal-title":"Information and Computation"},{"key":"2700_CR20","doi-asserted-by":"crossref","unstructured":"Peters D. Single-peakedness and total unimodularity: new polynomial-time algorithms for multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 1169\u20131176","DOI":"10.1609\/aaai.v32i1.11460"},{"key":"2700_CR21","unstructured":"Elkind E, Lackner M. Structure in dichotomous preferences. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2015, 2019\u20132025"},{"key":"2700_CR22","unstructured":"Liu H, Guo J. Parameterized complexity of winner determination in minimax committee elections. In: Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems. 2016, 341\u2013349"},{"key":"2700_CR23","doi-asserted-by":"crossref","unstructured":"Yang Y. On the tree representations of dichotomous preferences. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 644\u2013650","DOI":"10.24963\/ijcai.2019\/91"},{"key":"2700_CR24","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1613\/jair.3896","volume":"47","author":"N Betzler","year":"2013","unstructured":"Betzler N, Slinko A, Uhlmann J. On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 2013, 47: 475\u2013519","journal-title":"Journal of Artificial Intelligence Research"},{"key":"2700_CR25","doi-asserted-by":"publisher","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. The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 2015, 569: 43\u201357","journal-title":"Theoretical Computer Science"},{"key":"2700_CR26","unstructured":"Elkind E, Lackner M, Peters D. Structured preferences. In: Endriss U, ed. Trends in Computational Social Choice. AI Access, 2017, 187\u2013207"},{"key":"2700_CR27","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-47904-9_5","volume-title":"Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division","author":"E Hemaspaandra","year":"2016","unstructured":"Hemaspaandra E, Hemaspaandra L A, Rothe J. The complexity of manipulative actions in single-peaked societies. In: Rothe J, ed. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Berlin: Springer, 2016, 327\u2013360"},{"issue":"9","key":"2700_CR28","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1134\/S0005117922090016","volume":"83","author":"A V Karpov","year":"2022","unstructured":"Karpov A V. Structured preferences: A literature survey. Automation and Remote Control, 2022, 83(9): 1329\u20131354","journal-title":"Automation and Remote Control"},{"key":"2700_CR29","unstructured":"Elkind E, Lackner M, Peters D. Preference restrictions in computational social choice: A survey. 2022, arXiv preprint arXiv: 2205.09092"},{"key":"2700_CR30","first-page":"27","volume":"98","author":"M Dom","year":"2009","unstructured":"Dom M. Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science, 2009, 98: 27\u201359","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"2700_CR31","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1613\/jair.1.11732","volume":"68","author":"D Peters","year":"2020","unstructured":"Peters D, Lackner M. Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 2020, 68: 463\u2013502","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3","key":"2700_CR32","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K S Booth","year":"1976","unstructured":"Booth K S, Lueker G S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 1976, 13(3): 335\u2013379","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2700_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"W L Hsu","year":"2002","unstructured":"Hsu W L. A simple test for the consecutive ones property. Journal of Algorithms, 2002, 43(1): 1\u201316","journal-title":"Journal of Algorithms"},{"key":"2700_CR34","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-319-21275-3_14","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. Lower bounds based on the exponential-time hypothesis. In: Cygan M, Fomin F V, Kowalik \u0141, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S, eds. Parameterized Algorithms. Cham: Springer, 2015, 467\u2013521"},{"key":"2700_CR35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"R G Downey","year":"2013","unstructured":"Downey R G, Fellows M R. Fundamentals of Parameterized Complexity. London: Springer, 2013"},{"key":"2700_CR36","volume-title":"Digraphs\u2014Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen J, Gutin G. Digraphs\u2014Theory, Algorithms and Applications. 2nd ed. London: Springer, 2009","edition":"2nd ed."},{"key":"2700_CR37","unstructured":"West D B. Introduction to Graph Theory. 2nd ed. Prentice Hall, 2001"},{"issue":"3","key":"2700_CR38","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S E Dreyfus","year":"1971","unstructured":"Dreyfus S E, Wagner R A. The Steiner problem in graphs. Networks, 1971, 1(3): 195\u2013207","journal-title":"Networks"},{"issue":"2","key":"2700_CR39","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/100794560","volume":"25","author":"J Guo","year":"2011","unstructured":"Guo J, Niedermeier R, Such\u00fd O. Parameterized complexity of arc-weighted directed Steiner problems. SIAM Journal on Discrete Mathematics, 2011, 25(2): 583\u2013599","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2700_CR40","doi-asserted-by":"crossref","unstructured":"Ding B, Yu J X, Wang S, Qin L, Zhang X, Lin X. Finding top-k mincost connected trees in databases. In: Proceedings of the 23rd International Conference on Data Engineering. 2007, 836\u2013845","DOI":"10.1109\/ICDE.2007.367929"},{"key":"2700_CR41","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund A, Husfeldt T, Kaski P, Koivisto M. Fourier meets M\u00f6bius: Fast subset convolution. In: Proceedings of the 39th ACM Symposium on Theory of Computing. 2007, 67\u201374","DOI":"10.1145\/1250790.1250801"},{"issue":"3","key":"2700_CR42","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00224-007-1324-4","volume":"41","author":"B Fuchs","year":"2007","unstructured":"Fuchs B, Kern W, Molle D, Richter S, Rossmanith P, Wang X. Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 2007, 41(3): 493\u2013500","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"2700_CR43","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom M, Lokshtanov D, Saurabh S. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 2014, 11(2): 13","journal-title":"ACM Transactions on Algorithms"},{"issue":"8","key":"2700_CR44","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen J, Huang X, Kanj I A, Xia G. Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 2006, 72(8): 1346\u20131367","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-023-2700-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-023-2700-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-023-2700-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T13:19:57Z","timestamp":1705929597000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-023-2700-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,22]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["2700"],"URL":"https:\/\/doi.org\/10.1007\/s11704-023-2700-1","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,22]]},"assertion":[{"value":"18 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"183402"}}