{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T19:13:33Z","timestamp":1767640413560,"version":"3.48.0"},"reference-count":41,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T00:00:00Z","timestamp":1738368000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2025,2,1]],"date-time":"2025-02-01T00:00:00Z","timestamp":1738368000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"FWF","award":["P32830"],"award-info":[{"award-number":["P32830"]}]},{"DOI":"10.13039\/501100001821","name":"WWTF","doi-asserted-by":"crossref","award":["ICT19-065"],"award-info":[{"award-number":["ICT19-065"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Argument &amp; Computation"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:p>Abstract argumentation has proven to be a versatile tool to model and analyze various problems in an argumentative setting. The addition of collective attacks syntactically extends Dung\u2019s original argumentation frameworks (AFs), while retaining the most desirable properties\u2014the resulting class of frameworks is called SETAFs. While most reasoning tasks in the realm of abstract argumentation have been shown to be intractable, real-world instances oftentimes are not entirely random but admit a certain structure that allows for efficient computational shortcuts. In certain cases, we can characterize this structure via an integer parameter, and exploit these insights with advanced algorithmic techniques. A thorough analysis of the computational aspects of SETAFs w.r.t. parameterized algorithms has not yet been conducted. We start the investigation of these approaches by applying the backdoor and treewidth approaches to SETAFs. A backdoor is a part of a problem instance, such that removing the backdoor leads to a simple structure. If we can find such a backdoor and guess the solution on this part (respectively, extensions), the rest of the solution follows almost effortlessly. Similarly, the treewidth of a problem instance is a parameter that characterizes the properties of the instance\u2019s graph structure. Intuitively, the lower the treewidth of a graph, the more \u201ctree-like\u201d it is. Since most argumentation problems become easy on trees, one can exploit low treewidth for efficient algorithms. In this paper, we establish that for SETAFs with constant backdoor sizes general argumentation tasks become efficiently solvable\u2014they are fixed-parameter tractable. We generalize the respective techniques that are known for the special case of Dung-style AFs and show that they also apply to the more general case of SETAFs. In addition, we can show an improvement in the asymptotic runtime compared to earlier approaches for AFs via two-valued guesses instead of the state-of-the-art three-valued approach. Along the way, we point out similarities and interesting situations arising from the more general setting. While treewidth is well-studied in the context of AFs with their graph structure, it cannot be directly applied to the (directed) hypergraphs representing SETAFs. We thus introduce two generalizations of treewidth based on different graphs that can be associated with SETAFs, that is, the primal graph and the incidence graph. We show that while some of these notions allow for parameterized tractability results, reasoning remains intractable for other notions, even if we fix the parameter to a small constant. We present parameterized algorithms for efficient reasoning on SETAFs via tree decompositions by characterizing extensions not only by labeling the arguments, but also by assigning (temporary) labels to the attacks.<\/jats:p>","DOI":"10.1177\/19462174251319186","type":"journal-article","created":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:10:10Z","timestamp":1742951410000},"page":"36-93","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized complexity of abstract argumentation with collective attacks"],"prefix":"10.1177","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2269-8193","authenticated-orcid":false,"given":"Wolfgang","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0205-0039","authenticated-orcid":false,"given":"Matthias","family":"K\u00f6nig","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}]},{"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}]}],"member":"179","published-online":{"date-parts":[[2025,3,25]]},"reference":[{"key":"e_1_3_6_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00041-X"},{"key":"e_1_3_6_3_2","doi-asserted-by":"crossref","unstructured":"Nielsen SH Parsons S. A generalization of Dung\u2019s abstract framework for argumentation: arguing with sets of attacking arguments. In: Proceedings of ArgMAS 2006. Springer 2006 pp.54\u201373.","DOI":"10.1007\/978-3-540-75526-5_4"},{"key":"e_1_3_6_4_2","doi-asserted-by":"crossref","unstructured":"Coste-Marquis S Devred C Marquis P. Symmetric argumentation frameworks. In: Proceedings of ECSQARU 2005 LNCS Vol. 3571. Springer 2005 pp.317\u2013328.","DOI":"10.1007\/11518655_28"},{"key":"e_1_3_6_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.03.006"},{"key":"e_1_3_6_6_2","unstructured":"Dunne PE Bench-Capon TJM. Complexity and combinatorial properties of argument systems. Technical Report Department of Computer Science University of Liverpool 2001."},{"key":"e_1_3_6_7_2","unstructured":"Dvo\u0159\u00e1k W Gre\u00dfler A Woltran S. Evaluating SETAFs via answer-set programming. In: Proceedings of SAFA 2018 CEUR workshop proceedings Vol. 2171. CEUR-WS.org 2018 pp.10\u201321."},{"key":"e_1_3_6_8_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W K\u00f6nig M Woltran S. On the complexity of preferred semantics in argumentation frameworks with bounded cycle length. In: Proceedings of KR 2021 2021 pp.671\u2013675.","DOI":"10.24963\/kr.2021\/67"},{"key":"e_1_3_6_9_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W K\u00f6nig M Woltran S. Treewidth for argumentation frameworks with collective attacks. In: Proceedings of COMMA 2022 frontiers in artificial intelligence and applications Vol. 353. IOS Press 2022 pp.140\u2013151.","DOI":"10.3233\/FAIA220148"},{"key":"e_1_3_6_10_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W K\u00f6nig M Woltran S. Deletion-backdoors for argumentation frameworks with collective attacks. In: Proceedings of SAFA 2022 CEUR workshop proceedings Vol. 3236. CEUR-WS.org 2022 pp.98\u2013110.","DOI":"10.3233\/FAIA220148"},{"key":"e_1_3_6_11_2","first-page":"1","article-title":"Principles and their computational consequences for argumentation frameworks with collective attacks","volume":"100","author":"Dvo\u0159\u00e1k W","year":"2024","unstructured":"Dvo\u0159\u00e1k W, K\u00f6nig M, Ulbricht M, et al. Principles and their computational consequences for argumentation frameworks with collective attacks. J Artif Intell Res 2024; 100: 1\u20132.","journal-title":"J Artif Intell Res"},{"key":"e_1_3_6_12_2","doi-asserted-by":"crossref","unstructured":"Gaspers S Misra N Ordyniak S et al. Backdoors into heterogeneous classes of SAT and CSP. In: Proceedings of AAAI. AAAI Press 2014 pp.2652\u20132658.","DOI":"10.1609\/aaai.v28i1.9111"},{"key":"e_1_3_6_13_2","unstructured":"Gaspers S Ordyniak S Szeider S. Backdoor sets for CSP. In: The constraint satisfaction problem: complexity and approximability Dagstuhl follow-ups Vol. 7. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2017 pp.137\u2013157."},{"key":"e_1_3_6_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.12.001"},{"key":"e_1_3_6_15_2","doi-asserted-by":"crossref","unstructured":"Ordyniak S Schidler A Szeider S. Backdoor DNFs. In: Proceedings of IJCAI 2021. ijcai.org 2021 pp.1403\u20131409.","DOI":"10.24963\/ijcai.2021\/194"},{"key":"e_1_3_6_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.002"},{"key":"e_1_3_6_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.005"},{"key":"e_1_3_6_18_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W Szeider S Woltran S. Abstract argumentation via monadic second order logic. In: Proceedings of SUM 2012 LNCS Vol. 7520. Springer 2012 pp.85\u201398.","DOI":"10.1007\/978-3-642-33362-0_7"},{"key":"e_1_3_6_19_2","unstructured":"Charwat G. Tree-decomposition based algorithms for abstract argumentation frameworks. Master\u2019s thesis TU Wien 2012 http:\/\/permalink.obvsg.at\/AC07812654."},{"key":"e_1_3_6_20_2","unstructured":"Bliem B Hecher M Woltran S. On efficiently enumerating semi-stable extensions via dynamic programming on tree decompositions. In: Baroni P Gordon TF Scheffler T and Stede M (eds) Computational models of argument\u2014proceedings of COMMA 2016 Potsdam Germany 12\u201316 September 2016 Frontiers in artificial intelligence and applications Vol. 287. IOS Press 2016 pp.107\u2013118."},{"key":"e_1_3_6_21_2","doi-asserted-by":"crossref","unstructured":"Fichte JK Hecher M Mahmood Y et al. Decomposition-guided reductions for argumentation and treewidth. In: Proceedings of IJCAI 2021 2021 pp.1880\u20131886.","DOI":"10.24963\/ijcai.2021\/259"},{"key":"e_1_3_6_22_2","doi-asserted-by":"crossref","unstructured":"Popescu A Wallner JP. Reasoning in assumption-based argumentation using tree-decompositions. In: Proceedings of JELIA 2023 LNCS Vol. 14281 Springer 2023 pp.192\u2013208.","DOI":"10.1007\/978-3-031-43619-2_14"},{"key":"e_1_3_6_23_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W Hecher M K\u00f6nig M et al. Tractable abstract argumentation via backdoor-treewidth. In: Proceedings of AAAI 2022 pp.5608\u20135615.","DOI":"10.1609\/aaai.v36i5.20501"},{"key":"e_1_3_6_24_2","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k W K\u00f6nig M Woltran S. Graph-classes of argumentation frameworks with collective attacks. In: Proceedings of JELIA 2021 LNCS Vol. 12678. Springer 2021 pp.3\u201317.","DOI":"10.1007\/978-3-030-75775-5_1"},{"key":"e_1_3_6_25_2","unstructured":"Dvo\u0159\u00e1k W Dunne PE. Computational problems in formal argumentation and their complexity. In: Handbook of formal argumentation. College Publications 2018 pp.631\u2013687 Chapter 14."},{"key":"e_1_3_6_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2019.03.006"},{"key":"e_1_3_6_27_2","first-page":"1","article-title":"Attack semantics and collective attacks revisited","author":"Caminada M","year":"2024","unstructured":"Caminada M, K\u00f6nig M, Rapberger A, et al. Attack semantics and collective attacks revisited. Arg Comput 2024: Pre-press: 1\u201377.","journal-title":"Arg Comput"},{"key":"e_1_3_6_28_2","doi-asserted-by":"crossref","unstructured":"Baumann R Berthold M. Limits and possibilities of forgetting in abstract argumentation. In: Proceedings IJCAI 2022. ijcai.org 2022 pp.2539\u20132545.","DOI":"10.24963\/ijcai.2022\/352"},{"key":"e_1_3_6_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411511"},{"key":"e_1_3_6_30_2","doi-asserted-by":"crossref","unstructured":"Abboud A Williams VV. Popular conjectures imply strong lower bunds for dynamic problems. In: Proceedings of FOCS 2014 pp.434\u2013443.","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_6_31_2","doi-asserted-by":"crossref","unstructured":"Impagliazzo R Paturi R. Complexity of k-SAT. In: Proceedings of CCC 1999 1999 pp.237\u2013240.","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_3_6_32_2","doi-asserted-by":"crossref","unstructured":"Impagliazzo R Paturi R Zane F. Which problems have strongly exponential complexity? In: Proceedings of FOCS 1998 pp.653\u2013662.","DOI":"10.1109\/SFCS.1998.743516"},{"key":"e_1_3_6_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_6_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_6_35_2","doi-asserted-by":"crossref","unstructured":"Abseher M Musliu N Woltran S. HTD \u2013 A free open-source framework for (customized) tree decompositions and beyond. In: Proceedings of CPAIOR 2017. Springer 2017 pp.376\u2013386.","DOI":"10.1007\/978-3-319-59776-8_30"},{"key":"e_1_3_6_36_2","unstructured":"Courcelle B. Recognizability and second-order definability for sets of finite graphs. Technical Report I-8634 Universit\u00e9 de Bordeaux 1987."},{"key":"e_1_3_6_37_2","doi-asserted-by":"crossref","unstructured":"Courcelle B. Graph rewriting: an algebraic and logic approach. In: Handbook of theoretical computer science Vol. B. Amsterdam: Elsevier 1990 pp.193\u2013242.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"e_1_3_6_38_2","volume-title":"Treewidth, computations and approximations. LNCS","author":"Kloks T","year":"1994","unstructured":"Kloks T. Treewidth, computations and approximations. LNCS, Vol. 842. Springer, 1994."},{"key":"e_1_3_6_39_2","doi-asserted-by":"crossref","unstructured":"Villata S Boella G van der Torre LWN. Attack semantics for abstract argumentation. In: Proceedings of IJCAI 2011. IJCAI\/AAAI 2011 pp.406\u2013413.","DOI":"10.3233\/978-1-60750-619-5-111"},{"key":"e_1_3_6_40_2","doi-asserted-by":"crossref","unstructured":"Jakl M Pichler R Woltran S. Answer-set programming with bounded treewidth. In: Proceedings of IJCAI 2009 2009 pp.816\u2013822.","DOI":"10.1007\/978-3-642-04238-6_22"},{"key":"e_1_3_6_41_2","doi-asserted-by":"crossref","unstructured":"Fichte JK Hecher M Meier A. Counting complexity for reasoning in abstract argumentation. In: Proceedings of AAAI 2019. AAAI Press 2019 pp.2827\u20132834.","DOI":"10.1609\/aaai.v33i01.33012827"},{"key":"e_1_3_6_42_2","doi-asserted-by":"crossref","unstructured":"Dimopoulos Y Dvo\u0159\u00e1k W K\u00f6nig M et al. Redefining ABA+ semantics via abstract set-to-set attacks. In: Proceedings of AAAI 2024. AAAI Press 2024 pp.10493\u201310500.","DOI":"10.1609\/aaai.v38i9.28918"}],"container-title":["Argument &amp; Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/19462174251319186","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/19462174251319186","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/19462174251319186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,5]],"date-time":"2026-01-05T15:32:50Z","timestamp":1767627170000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/19462174251319186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.1177\/19462174251319186"],"URL":"https:\/\/doi.org\/10.1177\/19462174251319186","relation":{},"ISSN":["1946-2166","1946-2174"],"issn-type":[{"type":"print","value":"1946-2166"},{"type":"electronic","value":"1946-2174"}],"subject":[],"published":{"date-parts":[[2025,2]]}}}