{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T05:16:52Z","timestamp":1767676612505},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:p>Argumentation frameworks are a core formalism in the field of formal argumentation, with several semantics being proposed in the literature. Among them, preferred semantics is one of the most popular but comes with relatively high complexity.  In fact,\tdeciding whether an argument is skeptically accepted, i.e. contained in each preferred extension, is Pi^P_2-complete. In this work we study the complexity of  this problem w.r.t. the length of the cycles in the considered AF.\n\nOur results show which bounds are necessary to decrease the complexity to coNP and P, respectively. We also consider argumentation frameworks with collective attacks and achieve Pi^P_2-hardness already for cycles of length 4.<\/jats:p>","DOI":"10.24963\/kr.2021\/67","type":"proceedings-article","created":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:45:56Z","timestamp":1633970756000},"page":"671-675","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length"],"prefix":"10.24963","author":[{"given":"Wolfgang","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[{"name":"TU Wien"}]},{"given":"Matthias","family":"K\u00f6nig","sequence":"additional","affiliation":[{"name":"TU Wien"}]},{"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[{"name":"TU Wien"}]}],"member":"10584","event":{"number":"18","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Sea AI Lab","Potassco Solutions","European Association for Artificial Intelligence"],"acronym":"KR-2021","name":"18th International Conference on Principles of Knowledge Representation and Reasoning {KR-2021}","start":{"date-parts":[[2020,11,12]]},"theme":"Artificial Intelligence","location":"Hanoii, Vietnam","end":{"date-parts":[[2021,11,18]]}},"container-title":["Proceedings of the Eighteenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T16:46:30Z","timestamp":1633970790000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2021\/67"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2021\/67","relation":{},"subject":[],"published":{"date-parts":[[2021,9]]}}}