{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T03:44:22Z","timestamp":1777434262743,"version":"3.51.4"},"reference-count":39,"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-nc\/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"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Argument & Computation"],"published-print":{"date-parts":[[2025,2]]},"abstract":"\n This research explores the relationship between the bounded in-degree and out-degree of an argumentation framework and the computational complexity of the problems of Credulous Acceptance (\n CredA<\/jats:sans-serif>\n ) and Skeptical Acceptance (\n SkepA<\/jats:sans-serif>\n ) under preferred extensions. Researchers have studied the complexity of these problems when the in-degree\n \n \n (<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula>\n and out-degree\n \n \n (<\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula>\n of the arguments are restricted to\n \n \n 2<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n . Despite this restriction, the computational complexities of\n CredA<\/jats:sans-serif>\n and\n SkepA<\/jats:sans-serif>\n persist. Based on these results, we presents new results that provide deeper insights into the impact of additional constraints on the argumentation framework. Specifically, we show that when \u201c\n \n \n p<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d or \u201c\n \n \n q<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d is restricted to\n \n \n 1<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n , both problems\n CredA<\/jats:sans-serif>\n and\n SkepA<\/jats:sans-serif>\n can be solved in polynomial time. Subsequently, we impose additional constraints on the argumentation framework by analyzing the quantities \u201c\n \n \n a<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n ,\u201d \u201c\n \n \n b<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n ,\u201d and \u201c\n \n \n c<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n .\u201d For an argumentation framework\n \n \n A<\/mml:mi>\n F<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n and all arguments \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d of\n \n \n A<\/mml:mi>\n F<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n , the parameter \u201c\n \n \n a<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d indicates the maximum number of attackers that any argument \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d can have among all those that are not attacked by \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d\n \n \n A<\/mml:mi>\n F<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n , \u201c\n \n \n b<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d indicates the maximum number of arguments that any argument \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d attacks among all those that do not attack \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d, and\u00a0\u201c\n \n \n c<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d denotes the maximum number of arguments that any argument \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d attacks among those that attack \u201c\n \n \n x<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d. Surprisingly, even when all these quantities are restricted to\n \n \n 1<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n , the computational complexity of\n CredA<\/jats:sans-serif>\n persists. Furthermore, we explore the influence of symmetric attacks by fixing \u201c\n \n \n c<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d to zero, while setting \u201c\n \n \n a<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d and \u201c\n \n \n b<\/mml:mi>\n <\/mml:math>\n <\/jats:inline-formula>\n \u201d to\n \n \n 2<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>\n . Remarkably, the complexity of\n CredA<\/jats:sans-serif>\n persists under this restriction as well.\n <\/jats:p>","DOI":"10.1177\/19462174241306715","type":"journal-article","created":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T03:09:15Z","timestamp":1739502555000},"page":"108-129","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Analyzing the impact of bounded degree constraints on computational complexity of argumentation frameworks"],"prefix":"10.1177","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5782-4639","authenticated-orcid":false,"given":"Mohammed","family":"Elaroussi","sequence":"first","affiliation":[{"name":"Facult\u00e9 des Sciences Exactes, Unit\u00e9 de Recherche LaMOS, Universit\u00e9 de Bejaia, Bejaia, Algeria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,2,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00041-X"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"Bench-Capon T Prakken H Sartor G. Argumentation in legal reasoning. In: Simari G and Rahwan I (eds) Argumentation in artificial intelligence. Boston MA: Springer 2009 pp.363\u2013382.","DOI":"10.1007\/978-0-387-98197-0_18"},{"key":"e_1_3_3_4_2","volume-title":"Argumentation in artificial intelligence","author":"Rahwan I","year":"2009","unstructured":"Rahwan I, Simari GR. Argumentation in artificial intelligence, vol. 47, Heidelberg: Springer, 2009."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-008-9074-5"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.10.004"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.3233\/AAC-160013"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-014-0307-2"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2014.03.046"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2015.09.027"},{"key":"e_1_3_3_11_2","first-page":"403","article-title":"Empowering recommendation technologies through argumentation","author":"Ches\u00f1evar C","year":"2009","unstructured":"Ches\u00f1evar C, Maguitman AG, Gonz\u00e1lez MP. Empowering recommendation technologies through argumentation. Argum Artif Intell 2009; 403\u2013422.","journal-title":"Argum Artif Intell"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Doutre S Mengin J. Preferred extensions of argumentation frameworks: query answering and computation. In: Gor\u00e9 R Leitsch A and Nipkow T (eds) Automated reasoning. IJCAR 2001 Lecture notes in computer science vol. 2083. Berlin: Springer 2001 pp.272\u2013288.","DOI":"10.1007\/3-540-45744-5_20"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00261-8"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.3.377"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"Doutre S Mengin J. On sceptical versus credulous acceptance for abstract argument systems. In: 9th European conference on logics in artificial intelligence JELIA 2004. Berlin: Springer 2004 pp.462\u2013473.","DOI":"10.1007\/978-3-540-30227-8_39"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.03.006"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.002"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.10.001"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.11.001"},{"key":"e_1_3_3_20_2","first-page":"2557","article-title":"Computational problems in formal argumentation and their complexity","volume":"4","author":"Dvor\u00e1k W","year":"2017","unstructured":"Dvor\u00e1k W, Dunne PE. Computational problems in formal argumentation and their complexity. J Appl Logics-Ifcolog J Logics Appl 2017; 4: 2557\u20132622.","journal-title":"J Appl Logics-Ifcolog J Logics Appl"},{"key":"e_1_3_3_21_2","unstructured":"Baumeister D Neugebauer D Rothe J. Credulous and skeptical acceptance in incomplete argumentation frameworks. In: 9th international conference on computational models of arguments. Frontiers in Artificial Intelligence and Applications IOS Press 2018 pp.181\u2013192."},{"key":"e_1_3_3_22_2","first-page":"181","article-title":"Credulous and skeptical acceptability in probabilistic abstract argumentation: Complexity results","volume":"12","author":"Fazzinga B","year":"2018","unstructured":"Fazzinga B, Flesca S, Furfaro F. Credulous and skeptical acceptability in probabilistic abstract argumentation: Complexity results. Intell Artif 2018; 12: 181\u2013191.","journal-title":"Intell Artif"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.3233\/AAC-200907"},{"key":"e_1_3_3_24_2","first-page":"200118","article-title":"Explaining semantics and extension membership in abstract argumentation","volume":"16","author":"Besnard P","year":"2022","unstructured":"Besnard P, Doutre S, Duchatelle T, et\u00a0al. Explaining semantics and extension membership in abstract argumentation. Intell Syst Appl 2022; 16: 200118.","journal-title":"Intell Syst Appl"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)80707-9"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","unstructured":"Coste-Marquis S Devred C Marquis P. Symmetric argumentation frameworks. In: Godo L (ed.) Proceedings of the 8th European conference on symbolic and quantitative approaches to reasoning with uncertainty ECSQARU 2005 in Lecture Notes in Computer Science vol. 3571. Springer 2005 pp.317\u2013328.","DOI":"10.1007\/11518655_28"},{"key":"e_1_3_3_27_2","unstructured":"Dunne PE Bench-Capon TJ. Complexity and combinatorial properties of argument systems. University of Liverpool Department of Computer Science (ULCS) Technical report 2001."},{"key":"e_1_3_3_28_2","doi-asserted-by":"crossref","unstructured":"Thimm M Cerutti F Vallati M et al. Skeptical reasoning with preferred semantics in abstract argumentation without computing preferred extensions. In: Proceedings of the thirtieth international joint conference on artificial intelligence IJCAI 2021. ijcai.org 2021 pp.2069\u20132075.","DOI":"10.24963\/ijcai.2021\/285"},{"key":"e_1_3_3_29_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 the seventeenth international conference on principles of knowledge representation and reasoning KR 2021 2021 pp.671\u2013675.","DOI":"10.24963\/kr.2021\/67"},{"key":"e_1_3_3_30_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 the AAAI conference on artificial intelligence. AAAI Press 2022 pp.5608\u20135615.","DOI":"10.1609\/aaai.v36i5.20501"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00015-5"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888911000166"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.07.006"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-0018-1"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.03.018"},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","unstructured":"Wild M. Computations with finite closure systems and implications. In: Proceedings of the first annual international conference on computing and combinatorics LNCS vol. 959. Springer 1995 pp.111\u2013120.","DOI":"10.1007\/BFb0030825"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-023-09873-y"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106354"},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","unstructured":"Cook SA. The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing. New York: ACM Press 1971 pp.151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1976.233819"}],"container-title":["Argument & Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/19462174241306715","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/19462174241306715","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/19462174241306715","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T11:53:28Z","timestamp":1777377208000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/19462174241306715"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["10.1177\/19462174241306715"],"URL":"https:\/\/doi.org\/10.1177\/19462174241306715","relation":{},"ISSN":["1946-2166","1946-2174"],"issn-type":[{"value":"1946-2166","type":"print"},{"value":"1946-2174","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2]]}}}