Document Open Access Logo

Enumeration of Preferred Extensions in Almost Oriented Digraphs

Authors Serge Gaspers, Ray Li

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.74.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Serge Gaspers
  • UNSW Sydney, Sydney, Australia
  • Data61, CSIRO, Australia
Ray Li
  • UNSW Sydney, Sydney, Australia

Acknowledgements

We thank Oliver Fisher for fruitful discussions and collaboration on preliminary results in the early stages of this work.

Cite AsGet BibTex

Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.74

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 * 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).

Subject Classification

ACM Subject Classification
  • Computing methodologies → Knowledge representation and reasoning
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Enumeration
Keywords
  • abstract argumentation
  • exact algorithms
  • exponential time algorithms
  • parameterized algorithms
  • enumeration algorithms
  • semikernels in digraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Leila Amgoud and Claudette Cayrol. A Reasoning Model Based 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.
  2. Cyril Banderier, Jean-Marie Le Bars, and Vlady Ravelomanana. Generating functions for kernels of digraphs (Enumeration & asymptotics for a constraint from game theory). In Proceedings of the 16th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2004), pages 91-105, 2004. Google Scholar
  3. Ringo Baumann and Hannes Strass. Open Problems in Abstract Argumentation. In Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation - Essays Dedicated to Gerhard Brewka on the Occasion of His 60th Birthday, volume 9060 of Lecture Notes in Computer Science, pages 325-339. Springer, 2015. Google Scholar
  4. Trevor J. M. Bench-Capon. Value Based Argumentation Frameworks. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR 2002), volume cs.AI/0207059, pages 443-454, 2002. URL: http://arxiv.org/abs/cs.AI/0207059.
  5. Raymond Bisdorff. On enumerating the kernels in a bipolar-valued outranking digraph. Technical Report 6, Annales du Lamsade, 2006. hal-00118995. Google Scholar
  6. 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. Google Scholar
  7. Martin Caminada. An Algorithm for Computing Semi-stable Semantics. In Proceedings of the 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2007), volume 4724 of Lecture Notes in Computer Science, pages 222-234. Springer, 2007. Google Scholar
  8. Martin Caminada. An Algorithm for Computing Semi-stable Semantics. In ECSQARU 2007: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, volume 4724 of Lecture Notes in Computer Science, pages 222-234. Springer, Berlin, Heidelberg, 2007. Google Scholar
  9. Federico Cerutti, Paul E. Dunne, Massimiliano Giacomin, and Mauro Vallati. Computing Preferred Extensions in Abstract Argumentation: A SAT-Based Approach. In Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation (TAFA 2013), volume 8306 of Lecture Notes in Computer Science, pages 176-193. Springer, 2013. Google Scholar
  10. Federico Cerutti, Massimiliano Giacomin, and Mauro Vallati. Algorithm Selection for Preferred Extensions Enumeration. In Proceedings of the 5th International Conference on Computational Models of Argument (COMMA 2014), volume 266 of Frontiers in Artificial Intelligence and Applications, pages 221-232. IOS Press, 2014. Google Scholar
  11. Federico Cerutti, Mauro Vallati, and Massimiliano Giacomin. On the impact of configuration on abstract argumentation automated reasoning. International Journal of Approximate Reasoning, 92:120-138, 2018. Google Scholar
  12. Günther Charwat, Wolfgang Dvorák, Sarah Alice Gaggl, Johannes Peter Wallner, and Stefan Woltran. Methods for solving reasoning problems in abstract argumentation - A survey. Artificial Intelligence, 220:28-63, 2015. Google Scholar
  13. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  14. Sylvie Doutre and Jérôme 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. Google Scholar
  15. Phan Minh Dung. On the acceptability of arguments and its fundamental role in non-monotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77:321-357, 1995. Google Scholar
  16. Paul E. Dunne, Wolfgang Dvorák, Thomas Linsbichler, and Stefan Woltran. Characteristics of multiple viewpoints in abstract argumentation. Artificial Intelligence, 228:153-178, 2015. Google Scholar
  17. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket 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. Google Scholar
  18. 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. Google Scholar
  19. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. Google Scholar
  20. Hortensia Galeana-Sánchez and Xueliang Li. Semikernels and (k, l)-Kernels in Digraphs. SIAM Journal on Discrete Mathematics, 11(2):340-346, 1998. Google Scholar
  21. Hortensia Galeana-Sánchez and Victor Neumann-Lara. On kernels and semikernels of digraphs. Discrete Mathematics, 48(1):67-76, 1984. Google Scholar
  22. Serge Gaspers. Exponential time algorithms: Structures, measures, and bounds. PhD thesis, University of Bergen, 2008. Google Scholar
  23. Serge Gaspers and Edward J. Lee. Exact Algorithms via Multivariate Subroutines. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 69:1-69:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.69.
  24. Sanjay Modgil. Hierarchical Argumentation. In Proceedings of the 10th European Conference on Logics in Artificial Intelligence (JELIA 2006), pages 319-332, 2006. URL: https://doi.org/10.1007/11853886_27.
  25. Sanjay Modgil and Martin Caminada. Proof Theories and Algorithms for Abstract Argumentation Frameworks. In Argumentation in Artificial Intelligence, pages 105-129. Springer, 2009. Google Scholar
  26. Sanjay Modgil and Henry Prakken. Resolutions in Structured 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. Google Scholar
  27. Victor Neumann-Lara. Seminúcleos de una digráfica. Technical report, Anales del Instituto de Matemáticas II, Universidad Nacional Autónoma México, 1971. Google Scholar
  28. Samer Nofal, Katie Atkinson, and Paul E. Dunne. Algorithms for decision problems in argument systems under preferred semantics. Artificial Intelligence, 207:23-51, 2014. Google Scholar
  29. Jayme Luiz Szwarcfiter and Guy Chaty. Enumerating the Kernels of a Directed Graph with no Odd Circuits. Information Processing Letters, 51(3):149-153, 1994. Google Scholar
  30. Mauro Vallati, Federico Cerutti, and Massimiliano Giacomin. Argumentation Extensions Enumeration as a Constraint Satisfaction Problem: a Performance Overview. In Proceedings of the International Workshop on Defeasible and Ampliative Reasoning (DARe@ECAI 2014), volume 1212 of CEUR Workshop Proceedings. CEUR-WS.org, 2014. Google Scholar
  31. Mauro Vallati, Federico Cerutti, and Massimiliano Giacomin. Argumentation Frameworks Features: an Initial Study. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), volume 263 of Frontiers in Artificial Intelligence and Applications, pages 1117-1118. IOS Press, 2014. Google Scholar
  32. John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact