pith. sign in

arxiv: 1907.01006 · v1 · pith:HPME2B22new · submitted 2019-07-01 · 💻 cs.DS · cs.DM· math.CO

Enumeration of Preferred Extensions in Almost Oriented Digraphs

Serge Gaspers , Ray Li This is my paper

Pith reviewed 2026-05-25 11:18 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.CO
keywords preferred extensionsenumeration algorithmsdirected graphsoriented graphsargumentation frameworksmaximal semikernelsmonotone local search
0
0 comments X

The pith

All preferred extensions of a directed graph on n vertices can be enumerated in O*(3^{n/3}) time with a matching lower bound of Ω(3^{n/3}).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives algorithms to list every preferred extension in any directed graph on n vertices in O*(3^{n/3}) time and shows some graphs require at least that many steps because they contain that many extensions. For oriented graphs that contain no 2-cycles the time drops to O(1.2321^n) while the lower bound remains Ω(3^{n/6}). The same task is equivalent to enumerating all maximal semikernels, which directly gives all maximal consistent sets of arguments in an abstract argumentation framework. The authors reach these times by combining three separate algorithms, with the key new piece being a 2-stage sampling procedure analyzed via monotone local search.

Core claim

For directed graphs the enumeration of all preferred extensions runs in O*(3^{n/3}) time and some graphs achieve Ω(3^{n/3}) extensions. For oriented graphs the time improves to O(1.2321^n) with a lower bound of Ω(3^{n/6}) > Ω(1.2009^n). A new 2-stage sampling algorithm together with a parameterized enumeration routine, analyzed by the monotone local search technique and its extension, produces the fastest running times once the number of vertices inside 2-cycles is bounded by 0.8004 n.

What carries the argument

The 2-stage sampling algorithm that reduces the enumeration of maximal semikernels to a monotone local search problem on digraphs whose 2-cycles are limited.

If this is right

  • Every digraph admits an enumeration algorithm bounded by O*(3^{n/3}).
  • Some digraphs require Ω(3^{n/3}) time simply because they possess that many preferred extensions.
  • Oriented graphs without 2-cycles admit an O(1.2321^n) enumeration algorithm.
  • Graphs whose vertices in 2-cycles form at most 0.8004 n admit tailored algorithms that improve on the general bound.
  • A linear combination of three algorithms covers every possible density of 2-cycles with the best available exponent.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The sampling-plus-local-search pattern may transfer to the enumeration of other maximal structures such as kernels or independent sets.
  • The concrete exponents could be used to benchmark practical solvers for abstract argumentation problems that arise in multi-agent reasoning.
  • Further improvement on the oriented-graph base would require either a tighter sampling distribution or a different parameterization of the search tree.

Load-bearing premise

The running-time analysis of the new 2-stage sampling algorithm correctly applies the monotone local search technique and its extension without hidden polynomial factors or unaccounted cases in the branching or sampling steps.

What would settle it

A directed graph on n vertices whose number of preferred extensions exceeds 3^{n/3} for arbitrarily large n, or a concrete run of the claimed algorithm that takes more than the stated time on an explicit family of instances.

Figures

Figures reproduced from arXiv: 1907.01006 by Ray Li, Serge Gaspers.

Figure 1
Figure 1. Figure 1: The graph depicts the base of the exponential runni [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Loopless Translation of V = {v1, v2}, E = {(v1, v1),(v1, v2)} Lemma 8. The admissible extensions of G are exactly the admissible extensions of the Loopless Translation G′ of G. Proof. The odd cycle among {l1, l2, l3} ensures none of l1, l2, l3 are in any admissible extension of G′ . Hence l1 can not be attacked in any admissible extension of G′ . Hence, no vertex with a self loop in G is in any admissible … view at source ↗
Figure 3
Figure 3. Figure 3: Simple Oriented Translation of v1 ↔ v2 → v3 An example translation of V = {v1, v2, v3}, E = {(v1, v2),(v2, v1),(v2, v3)} can be found in [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Extended Translation of {C1 = (z1 ∨ ¬z2)} The primary tool used to relate known complexity results to problems for Argumentation Frame￾works is a translation from Boolean formulae in Conjunctive Normal Form (CNF) to AFs that has been called the standard translation (see, e.g., [20]). We will need a slight variation of the standard translation that was used in [15]. Definition F.1 (Extended translation [15]… view at source ↗
Figure 5
Figure 5. Figure 5: Key vertices in Case 2 H.3 Base Case - Und = ∅ We need to enumerate all maximal admissible subsets of Und∪ Def = Def. By Invariant 2, G[Def] is a DAG. Hence by Lemma 4 there is exactly one maximal admissible subset of Def and we can find it in polynomial time. H.4 Case 1 - Total Degree ≥ 7 Let v be any vertex in G[Und] with total degree ≥ 7. We do a 2-way branch on whether to include v(Definition 4.1). Thi… view at source ↗
Figure 6
Figure 6. Figure 6: Example Fn for Theorem 10 Case 4.2 - Attackers of each vertex are adjacent In this subcase, each v ∈ C has degree (2, 2) with adjacent in-neighbors. We handle this case by showing that the graph G[C] has a very restricted structure. In particular, we show that G[C] must look like [PITH_FULL_IMAGE:figures/full_fig_p034_6.png] view at source ↗
read the original 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^*(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\cdot 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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims that preferred extensions (equivalently, maximal semikernels) of an argumentation framework on n vertices can be enumerated in O*(3^{n/3}) time for general digraphs, with a matching Ω(3^{n/3}) lower-bound construction. For digraphs with at most 0.8004n vertices in 2-cycles (including oriented graphs), faster algorithms are given; in particular, one algorithm for oriented graphs runs in O(1.2321^n) time and there exist oriented graphs with Ω(3^{n/6}) > Ω(1.2009^n) preferred extensions. The O(1.2321^n) result is obtained by combining a new 2-stage sampling procedure with a parameterized enumeration routine and applying the monotone local search technique (STOC 2016) together with its ICALP 2017 extension.

Significance. If the central claims hold, the work supplies the first non-trivial enumeration algorithms for preferred extensions that improve on the 3^{n/3} baseline when the number of 2-cycles is limited, together with tight upper and lower bounds for both the general and oriented cases. The introduction of a 2-stage sampling method analyzed via monotone local search constitutes a technical contribution that may be reusable for other enumeration problems on digraphs.

major comments (1)
  1. [Section describing the 2-stage sampling algorithm and its combination with monotone local search] The O(1.2321^n) claim for oriented graphs rests on the 2-stage sampling algorithm correctly satisfying the hypotheses of the monotone local search theorem. The manuscript must show explicitly (in the section presenting the sampling procedure and its analysis) that every maximal semikernel is hit with probability at least 2^{-O(n)} and that the sampling and branching steps introduce neither hidden polynomial factors nor unaccounted cases; otherwise the claimed improvement over 3^{n/3} does not follow.
minor comments (1)
  1. The abstract states explicit time bounds but the full derivation steps, branching analysis, and sampling probabilities are referenced only at a high level; adding a short table that lists the running times obtained by each of the three combined algorithms for different fractions of 2-cycle vertices would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to make the verification of the monotone local search hypotheses fully explicit. We address the comment below and will revise the manuscript to strengthen the presentation of the 2-stage sampling analysis.

read point-by-point responses

  1. Referee: [Section describing the 2-stage sampling algorithm and its combination with monotone local search] The O(1.2321^n) claim for oriented graphs rests on the 2-stage sampling algorithm correctly satisfying the hypotheses of the monotone local search theorem. The manuscript must show explicitly (in the section presenting the sampling procedure and its analysis) that every maximal semikernel is hit with probability at least 2^{-O(n)} and that the sampling and branching steps introduce neither hidden polynomial factors nor unaccounted cases; otherwise the claimed improvement over 3^{n/3} does not follow.

    Authors: We agree that the verification should be stated more explicitly to avoid any ambiguity. In the revised version we will insert a short dedicated subsection (or expanded paragraph) immediately after the description of the 2-stage sampling procedure. This subsection will (i) restate the precise hypotheses of the monotone local search theorem (STOC 2016) and its ICALP 2017 extension, (ii) prove that the two-stage sampler returns every maximal semikernel with probability at least 2^{-O(n)} by combining the independent sampling probabilities of the two stages, and (iii) verify that the subsequent branching routine contributes only the claimed exponential factor with no hidden polynomial multipliers or unaccounted base cases. The existing probability calculations already support these claims; the revision will simply make the mapping to the theorem hypotheses direct and self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on explicit analysis and external techniques

full rationale

The paper's time bounds are obtained via direct algorithmic construction (a new 2-stage sampling procedure plus parameterized enumeration) whose analysis invokes the external monotone local search technique from STOC 2016 and its ICALP 2017 extension. No step defines a quantity in terms of itself, renames a fitted parameter as a prediction, or reduces the central claim to a self-citation chain; the matching upper and lower bounds are established independently through explicit algorithms and graph constructions. The cited prior results are independent published techniques, satisfying the criteria for non-circular support.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, invented entities, or ad-hoc axioms are introduced; the work rests on standard graph-theoretic definitions and previously published algorithmic techniques whose correctness is taken as given.

pith-pipeline@v0.9.0 · 5746 in / 1172 out tokens · 22165 ms · 2026-05-25T11:18:02.606948+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    A reasoning model bas ed on the production of acceptable arguments

    Leila Amgoud and Claudette Cayrol. A reasoning model bas ed on the production of acceptable arguments. Annals of Mathematics and Artificial Intelligence , 34(1-3):197–215, 2002. URL: https://doi.org/10.1023/A:1014490210693, doi:10.1023/A:1014490210693

    work page doi:10.1023/a:1014490210693 2002

  2. [2]

    Generating functions for ker- nels of digraphs (enumeration & asymptotics for a constrain t from game theory)

    Cyril Banderier, Jean-Marie Le Bars, and Vlady Raveloma nana. Generating functions for ker- nels of digraphs (enumeration & asymptotics for a constrain t from game theory). In Proceedings of the 16th International Conference on Formal Power Series an d Algebraic Combinatorics (FPSAC 2004) , pages 91–105, 2004

    work page 2004

  3. [3]

    On the maximal and avera ge numbers of stable extensions

    Ringo Baumann and Hannes Strass. On the maximal and avera ge numbers of stable extensions. In Proceedings of the 2nd International Workshop on Theory and Ap plications of Formal Ar- gumentation (TAF A 2013), volume 8306 of Lecture Notes in Computer Science , pages 111–126. Springer, 2013. 36

    work page 2013

  4. [4]

    Open problems in abstra ct argumentation

    Ringo Baumann and Hannes Strass. Open problems in abstra ct argumentation. In Advances in Knowledge Representation, Logic Programming, and Abstr act Argumentation - Essays Ded- icated to Gerhard Brewka on the Occasion of His 60th Birthday , volume 9060 of Lecture Notes in Computer Science , pages 325–339. Springer, 2015

    work page 2015

  5. [5]

    Trevor J. M. Bench-Capon. Value based argumentation fra meworks. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR 200 2), volume cs.AI/0207059, pages 443–454, 2002. URL: http://arxiv.org/abs/cs.AI/0207059

    work page arXiv 2002

  6. [6]

    On enumerating the kernels in a bipolar- valued outranking digraph

    Raymond Bisdorff. On enumerating the kernels in a bipolar- valued outranking digraph. Tech- nical Report 6, Annales du Lamsade, 2006. hal-00118995

    work page 2006

  7. [7]

    A comparative test on the enumeration of extensions in abstract argumentation

    Stefano Bistarelli, Fabio Rossi, and Francesco Santini . A comparative test on the enumeration of extensions in abstract argumentation. Fundamenta Informaticae, 140(3-4):263–278, 2015

    work page 2015

  8. [8]

    An algorithm for computing semi-stabl e semantics

    Martin Caminada. An algorithm for computing semi-stabl e semantics. In Proceedings of the 9th European Conference on Symbolic and Quantitative App roaches to Reasoning with Uncertainty (ECSQARU 2007) , volume 4724 of Lecture Notes in Computer Science , pages 222–234. Springer, 2007

    work page 2007

  9. [9]

    An algorithm for computing semi-stabl e semantics

    Martin Caminada. An algorithm for computing semi-stabl e semantics. In ECSQARU 2007: Symbolic and Quantitative Approaches to Reasoning with Unc ertainty, volume 4724 of Lecture Notes in Computer Science , pages 222–234. Springer, Berlin, Heidelberg, 2007

    work page 2007

  10. [10]

    Dunne, Massimiliano Giacomi n, and Mauro Vallati

    Federico Cerutti, Paul E. Dunne, Massimiliano Giacomi n, and Mauro Vallati. Computing preferred extensions in abstract argumentation: A sat-bas ed approach. In Proceedings of the 2nd International Workshop on Theory and Applications of Form al Argumentation (TAF A 2013), volume 8306 of Lecture Notes in Computer Science , pages 176–193. Springer, 2013

    work page 2013

  11. [11]

    Algorithm selection for preferred extensions enumeration

    Federico Cerutti, Massimiliano Giacomin, and Mauro Va llati. Algorithm selection for preferred extensions enumeration. In Proceedings of the 5th International Conference on Computatio nal Models of Argument (COMMA 2014) , volume 266 of Frontiers in Artificial Intelligence and Applications, pages 221–232. IOS Press, 2014

    work page 2014

  12. [12]

    On the impact of configura- tion on abstract argumentation automated reasoning

    Federico Cerutti, Mauro Vallati, and Massimiliano Gia comin. On the impact of configura- tion on abstract argumentation automated reasoning. International Journal of Approximate Reasoning, 92:120–138, 2018

    work page 2018

  13. [13]

    Methods for solving reasoning problems in abst ract argumentation - A survey

    G¨ unther Charwat, Wolfgang Dvor´ ak, Sarah Alice Gaggl , Johannes Peter Wallner, and Ste- fan Woltran. Methods for solving reasoning problems in abst ract argumentation - A survey. Artificial Intelligence , 220:28–63, 2015

    work page 2015

  14. [14]

    Fomin, /suppress Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha/suppress l Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, /suppress Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Micha/suppress l Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015

    work page 2015

  15. [15]

    Graph theoretica l structures in logic programs and default theories

    Yannis Dimopoulos and Albert Torres. Graph theoretica l structures in logic programs and default theories. Theoretical Computer Science , 170:209–224, 1996. 37

    work page 1996

  16. [16]

    Preferred extensions of argumentation frameworks: Query, answering, and computation

    Sylvie Doutre and J´ erˆ ome Mengin. Preferred extensions of argumentation frameworks: Query, answering, and computation. In Proceedings of the 1st International Joint Conference on Automated Reasoning (IJCAR 2001) , volume 2083 of Lecture Notes in Computer Science , pages 272–288. Springer, 2001

    work page 2001

  17. [17]

    On the acceptability of arguments and it s fundamental role in non- monotonic reasoning, logic programming and n-person games

    Phan Minh Dung. On the acceptability of arguments and it s fundamental role in non- monotonic reasoning, logic programming and n-person games . Artificial Intelligence , 77:321– 357, 1995

    work page 1995

  18. [18]

    Dunne, Wolfgang Dvor´ ak, Thomas Linsbichler, a nd Stefan Woltran

    Paul E. Dunne, Wolfgang Dvor´ ak, Thomas Linsbichler, a nd Stefan Woltran. Characteristics of multiple viewpoints in abstract argumentation. Artificial Intelligence , 228:153–178, 2015

    work page 2015

  19. [19]

    Dunne, Wolfgang Dvoˇ r´ ak, Thomas Linsbichler, and Stefan Woltran

    Paul E. Dunne, Wolfgang Dvoˇ r´ ak, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple viewpoints in abstract argumentation. Artificial Intelligence , 228:153–178, 2015

    work page 2015

  20. [20]

    Dunne and Michael Wooldridge

    Paul E. Dunne and Michael Wooldridge. Complexity of abs tract argumentation. In Iyad Rahwan and Guillermo R. Simari, editors, Argumentation in Artificial Intelligence , chapter 5, pages 85–104. Springer, Boston, MA, 2009

    work page 2009

  21. [21]

    Fomin, Serge Gaspers, Daniel Lokshtanov, and S aket Saurabh

    Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and S aket Saurabh. Exact algorithms via monotone local search. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) , pages 764–775. ACM, 2016

    work page 2016

  22. [22]

    Fomin, Fabrizio Grandoni, and Dieter Kratsch

    Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM , 56(5):25:1–25:32, 2009

    work page 2009

  23. [23]

    Fomin and Dieter Kratsch

    Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms . Springer, 2010

    work page 2010

  24. [24]

    Semikernels and ( k, l )-kernels in digraphs

    Hortensia Galeana-S´ anchez and Xueliang Li. Semikernels and ( k, l )-kernels in digraphs. SIAM Journal on Discrete Mathematics , 11(2):340–346, 1998

    work page 1998

  25. [25]

    Discrete Mathematics, 48(1):67–76, 1984

    Hortensia Galeana-S´ anchez and Victor Neumann-Lara.On kernels and semikernels of digraphs. Discrete Mathematics, 48(1):67–76, 1984

    work page 1984

  26. [26]

    Exponential time algorithms: Structures, measures, and bo unds

    Serge Gaspers. Exponential time algorithms: Structures, measures, and bo unds. PhD thesis, University of Bergen, 2008

    work page 2008

  27. [27]

    Serge Gaspers and Edward J. Lee. Exact Algorithms via Mu ltivariate Subrou- tines. In Proceedings of the 44th International Colloquium on Automata , Lan- guages, and Programming (ICALP 2017) , volume 80 of Leibniz International Pro- ceedings in Informatics (LIPIcs) , pages 69:1–69:13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. URL: http://dro...

    work page doi:10.4230/lipics.icalp.2017.69 2017

  28. [28]

    O n the complexity of enumerating the extensions of abstract argumentation frameworks

    Markus Kr¨ oll, Reinhard Pichler, and Stefan Woltran. O n the complexity of enumerating the extensions of abstract argumentation frameworks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017) , pages 1145–1152. ijcai.org, 2017

    work page 2017

  29. [29]

    Hierarchical argumentation

    Sanjay Modgil. Hierarchical argumentation. In Proceedings of the 10th European Con- ference on Logics in Artificial Intelligence (JELIA 2006) , pages 319–332, 2006. URL: https://doi.org/10.1007/11853886_27, doi:10.1007/11853886_27. 38

    work page doi:10.1007/11853886_27 2006

  30. [30]

    Proof theories and a lgorithms for abstract argumenta- tion frameworks

    Sanjay Modgil and Martin Caminada. Proof theories and a lgorithms for abstract argumenta- tion frameworks. In Argumentation in Artificial Intelligence , pages 105–129. Springer, 2009

    work page 2009

  31. [31]

    Resolutions in struct ured argumentation

    Sanjay Modgil and Henry Prakken. Resolutions in struct ured argumentation. In Proceedings of the 4th International Conference on Computational Models of Argument (COMMA 2012) , volume 245 of Frontiers in Artificial Intelligence and Applications , pages 310–321. IOS Press, 2012

    work page 2012

  32. [32]

    Moon and Leo Moser

    John W. Moon and Leo Moser. On cliques in graphs. Israel Journal of Mathematics , 3:23–28, 1965

    work page 1965

  33. [33]

    Semin´ ucleos de una digr´ afica

    Victor Neumann-Lara. Semin´ ucleos de una digr´ afica. T echnical report, Anales del Instituto de Matem´ aticas II, Universidad Nacional Aut´ onoma M´ exico, 1971

    work page 1971

  34. [34]

    Samer Nofal, Katie Atkinson, and Paul E. Dunne. Algorit hms for decision problems in argu- ment systems under preferred semantics. Artificial Intelligence , 207:23–51, 2014

    work page 2014

  35. [35]

    Enumerating the ke rnels of a directed graph with no odd circuits

    Jayme Luiz Szwarcfiter and Guy Chaty. Enumerating the ke rnels of a directed graph with no odd circuits. Information Processing Letters , 51(3):149–153, 1994

    work page 1994

  36. [36]

    Argumentation extensions enu- meration as a constraint satisfaction problem: a performan ce overview

    Mauro Vallati, Federico Cerutti, and Massimiliano Gia comin. Argumentation extensions enu- meration as a constraint satisfaction problem: a performan ce overview. In Proceedings of the International Workshop on Defeasible and Ampliative Reason ing (DARe@ECAI 2014) , volume 1212 of CEUR Workshop Proceedings. CEUR-WS.org, 2014

    work page 2014

  37. [37]

    Argumentation frameworks features: an initial study

    Mauro Vallati, Federico Cerutti, and Massimiliano Gia comin. Argumentation frameworks features: an initial study. In Proceedings of the 21st European Conference on Artificial Inte lli- gence (ECAI 2014) , volume 263 of Frontiers in Artificial Intelligence and Applications , pages 1117–1118. IOS Press, 2014

    work page 2014

  38. [38]

    Theory of Games and Economic Behavior

    John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior . Prince- ton University Press, 1944. 39

    work page 1944