Enumeration of Preferred Extensions in Almost Oriented Digraphs

DOI10.4230/LIPICS.MFCS.2019.74MaRDI QIDQ6321373arXivFDO

Authors Serge Gaspers, Ray Li

Publication date 1 July 2019

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2019.74

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Logic in artificial intelligence (68T27) Analysis of algorithms (68W40)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: 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^{\ast }(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.8004cdotn$ 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).

This page was built for publication: Enumeration of Preferred Extensions in Almost Oriented Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321373)