{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T01:30:49Z","timestamp":1785202249389,"version":"3.55.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["ME4279\/ 1-2"],"award-info":[{"award-number":["ME4279\/ 1-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2023,7,31]]},"abstract":"<jats:p>Argumentation is a well-established formalism dealing with conflicting information by generating and comparing arguments. It has been playing a major role in AI for decades. In logic-based argumentation, we explore the internal structure of an argument. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this article, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Creignou\u00a0et\u00a0al. 2014 and Parson\u00a0et\u00a0al., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: First, we consider all possible propositional fragments of the problem within Schaefer\u2019s framework (STOC 1978) and then study different parameterizations for each of the fragments. We identify a list of reasonable structural parameters (size of the claim, support, knowledge base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (para-NP and beyond).<\/jats:p>","DOI":"10.1145\/3582499","type":"journal-article","created":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T11:57:18Z","timestamp":1675166238000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Complexity of Logic-based Argumentation in Schaefer\u2019s Framework"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5651-5391","authenticated-orcid":false,"given":"Yasir","family":"Mahmood","sequence":"first","affiliation":[{"name":"Leibniz Universit\u00e4t Hannover, Institut f\u00fcr Theoretische Informatik, Hannover, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8061-5376","authenticated-orcid":false,"given":"Arne","family":"Meier","sequence":"additional","affiliation":[{"name":"Leibniz Universit\u00e4t Hannover, Institut f\u00fcr Theoretische Informatik, Hannover, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8551-1624","authenticated-orcid":false,"given":"Johannes","family":"Schmidt","sequence":"additional","affiliation":[{"name":"J\u00f6nk\u00f6ping University, Department of Computer Science and Informatics, School of Engineering, J\u00f6nk\u00f6ping, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.11.006"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v38i3.2704"},{"key":"e_1_3_1_4_2","volume-title":"Handbook of Formal Argumentation","author":"Baroni Pietro","year":"2018","unstructured":"Pietro Baroni, Dov Gabbay, Massimiliano Giacomin, and Leendert van der Torre (Eds.). 2018. Handbook of Formal Argumentation. College Publications."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00071-6"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/1373332"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.06.015"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.003"},{"key":"e_1_3_1_9_2","article-title":"Playing with Boolean blocks, part II: Constraint satisfaction problems","volume":"35","author":"B\u00f6hler Elmar","year":"2004","unstructured":"Elmar B\u00f6hler, Nadia Creignou, Steffen Reith, and Heribert Vollmer. 2004. Playing with Boolean blocks, part II: Constraint satisfaction problems. ACM SIGACT-Newslett. 35 (2004).","journal-title":"ACM SIGACT-Newslett."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/371578.371581"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629421"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","unstructured":"Nadia Creignou Sanjeev Khanna and Madhu Sudan. 2001. Complexity classifications of Boolean constraint satisfaction problems. In SIAM Monographs on Discrete Mathematics and Applications Vol. 7. SIAM.","DOI":"10.1137\/1.9780898718546"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12090189"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9702-4"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1080\/19462166.2011.629736"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_2"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00041-X"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/259"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012827"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.11.002"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36755-8_13"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exaa079"},{"key":"e_1_3_1_25_2","first-page":"6426","volume-title":"35th AAAI Conference on Artificial Intelligence, 33rd Conference on Innovative Applications of Artificial Intelligence, 11th Symposium on Educational Advances in Artificial Intelligence","author":"Mahmood Yasir","year":"2021","unstructured":"Yasir Mahmood, Arne Meier, and Johannes Schmidt. 2021. Parameterized complexity of logic-based argumentation in Schaefer\u2019s framework. In 35th AAAI Conference on Artificial Intelligence, 33rd Conference on Innovative Applications of Artificial Intelligence, 11th Symposium on Educational Advances in Artificial Intelligence. 6426\u20136434. Retrieved from: https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/16797."},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.15488\/9427"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.02.001"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.3.347"},{"key":"e_1_3_1_29_2","first-page":"1","article-title":"The two-valued iterative systems of mathematical logic","volume":"5","author":"Post Emil L.","year":"1941","unstructured":"Emil L. Post. 1941. The two-valued iterative systems of mathematical logic. Ann. Math. Stud. 5 (1941), 1\u2013122.","journal-title":"Ann. Math. Stud."},{"key":"e_1_3_1_30_2","first-page":"219","volume-title":"Logics for Defeasible Argumentation","author":"Prakken Henry","year":"2002","unstructured":"Henry Prakken and Gerard Vreeswijk. 2002. Logics for Defeasible Argumentation. Springer Netherlands, Dordrecht, 219\u2013318."},{"key":"e_1_3_1_31_2","first-page":"1949","volume-title":"International Joint Conference on Artificial Intelligence","author":"Rago Antonio","year":"2018","unstructured":"Antonio Rago, Oana Cocarascu, and Francesca Toni. 2018. Argumentation-Based recommendations: Fantastic explanations and how to find them. In International Joint Conference on Artificial Intelligence. ijcai.org, 1949\u20131955."},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_9"},{"key":"e_1_3_1_34_2","volume-title":"Introduction to the Theory of Computation","author":"Sipser Michael","year":"1997","unstructured":"Michael Sipser. 1997. Introduction to the Theory of Computation. PWS Publishing Company."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3582499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:50Z","timestamp":1750183730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3582499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3582499"],"URL":"https:\/\/doi.org\/10.1145\/3582499","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,10]]},"assertion":[{"value":"2021-10-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}