2026-07-27T21:43:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11018 2024-03-06T10:47:04Z ddc:004 open_access

Enumeration of Preferred Extensions in Almost Oriented Digraphs Gaspers, Serge Li, Ray abstract argumentation exact algorithms exponential time algorithms parameterized algorithms enumeration algorithms semikernels in digraphs In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a directed graph. For directed graphs on n vertices, all preferred extensions can be enumerated in O^*(3^{n/3}) time and there are directed graphs with Omega(3^{n/3}) preferred extensions. We give faster enumeration algorithms for directed graphs with at most 0.8004 * n vertices occurring in 2-cycles. In particular, for oriented graphs (digraphs with no 2-cycles) one of our algorithms runs in time O(1.2321^n), and we show that there are oriented graphs with Omega(3^{n/6}) > Omega(1.2009^n) preferred extensions. A combination of three algorithms leads to the fastest enumeration times for various proportions of the number of vertices in 2-cycles. The most innovative one is a new 2-stage sampling algorithm, combined with a new parameterized enumeration algorithm, analyzed with a combination of the recent monotone local search technique (STOC 2016) and an extension thereof (ICALP 2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Serge Gaspers and Ray Li 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.74 urn:nbn:de:0030-drops-110188 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.74 eng https://creativecommons.org/licenses/by/3.0/legalcode