×

Augmenting tractable fragments of abstract argumentation. (English) Zbl 1251.68225

Summary: We present a new approach to the efficient solution of important computational problems that arise in the context of abstract argumentation. Our approach makes known algorithms defined for restricted fragments generally applicable, at a computational cost that scales with the distance from the fragment. Thus, in a certain sense, we gradually augment tractable fragments. Surprisingly, it turns out that some tractable fragments admit such an augmentation and that others do not.
More specifically, we show that the problems of credulous and skeptical acceptance are fixed-parameter tractable when parameterized by the distance from the fragment of acyclic argumentation frameworks – for most semantics. Other tractable fragments such as the fragments of symmetrical and bipartite frameworks seem to prohibit an augmentation: the acceptance problems are already intractable for frameworks at distance 1 from the fragments.
For our study we use a broad setting and consider several different semantics. For the algorithmic results we utilize recent advances in fixed-parameter tractability.

MSC:

68T27 Logic in artificial intelligence
68Q25 Analysis of algorithms and problem complexity

Software:

OSCAR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baroni, P.; Dunne, P. E.; Giacomin, M., On the resolution-based family of abstract argumentation semantics and its grounded instance, Artificial Intelligence, 175, 791-813 (2011) · Zbl 1216.68255
[2] Baroni, P.; Giacomin, M., Semantics of abstract argument systems, (Rahwan, I.; Simari, G., Argumentation in Artificial Intelligence (2009), Springer Verlag), 25-44
[3] Bench-Capon, T. J.M.; Dunne, P. E., Argumentation in artificial intelligence, Artificial Intelligence, 171, 619-641 (2007) · Zbl 1168.68560
[4] Besnard, P.; Hunter, A., Elements of Argumentation (2008), The MIT Press
[5] Bondarenko, A.; Dung, P. M.; Kowalski, R. A.; Toni, F., An abstract, argumentation-theoretic approach to default reasoning, Artificial Intelligence, 93, 63-101 (1997) · Zbl 1017.03511
[6] Caminada, M., On the issue of reinstatement in argumentation, (Fisher, M.; van der Hoek, W.; Konev, B.; Lisitsa, A., Logics in Artificial Intelligence, Proceedings of the 10th European Conference, JELIA 2006. Logics in Artificial Intelligence, Proceedings of the 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006. Logics in Artificial Intelligence, Proceedings of the 10th European Conference, JELIA 2006. Logics in Artificial Intelligence, Proceedings of the 10th European Conference, JELIA 2006, Liverpool, UK, September 13-15, 2006, Lecture Notes in Computer Science, vol. 4160 (2006), Springer Verlag), 111-123 · Zbl 1152.68600
[7] Caminada, M., Semi-stable semantics, (Dunne, P. E.; Bench-Capon, T. J.M., Proceedings of the 1st Conference on Computational Models of Argument (COMMA 2006). Proceedings of the 1st Conference on Computational Models of Argument (COMMA 2006), Frontiers in Artificial Intelligence and Applications, vol. 144 (2006), IOS Press), 121-130
[8] Caminada, M.; Gabbay, D. M., A logical account of formal argumentation, Studia Logica, 93, 109-145 (2009) · Zbl 1188.03011
[9] Chen, J.; Liu, Y.; Lu, S.; OʼSullivan, B.; Razgon, I., A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55 (2008), Art. 21, 19
[10] Coste-Marquis, S.; Devred, C.; Marquis, P., Symmetric argumentation frameworks, (Godo, L., Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Proceedings of the 8th European Conference, ECSQARU 2005. Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Proceedings of the 8th European Conference, ECSQARU 2005, Barcelona, Spain, July 6-8, 2005. Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Proceedings of the 8th European Conference, ECSQARU 2005. Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Proceedings of the 8th European Conference, ECSQARU 2005, Barcelona, Spain, July 6-8, 2005, Lecture Notes in Computer Science, vol. 3571 (2005), Springer Verlag), 317-328 · Zbl 1122.68642
[11] Dimopoulos, Y.; Torres, A., Graph theoretical structures in logic programs and default theories, Theoret. Comput. Sci., 170, 209-244 (1996) · Zbl 0874.68190
[12] Downey, R. G.; Fellows, M. R., Parameterized Complexity, Monographs in Computer Science (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0914.68076
[13] Dung, P. M., On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and \(n\)-person games, Artificial Intelligence, 77, 321-357 (1995) · Zbl 1013.68556
[14] Dunne, P. E., Computational properties of argument systems satisfying graph-theoretic constraints, Artificial Intelligence, 171, 701-729 (2007) · Zbl 1168.68565
[15] P.E. Dunne, T.J.M. Bench-Capon, Complexity and combinatorial properties of argument systems, Technical Report, University of Liverpool, 2001.; P.E. Dunne, T.J.M. Bench-Capon, Complexity and combinatorial properties of argument systems, Technical Report, University of Liverpool, 2001.
[16] Dunne, P. E.; Bench-Capon, T. J.M., Coherence in finite argument systems, Artificial Intelligence, 141, 187-203 (2002) · Zbl 1043.68098
[17] Dunne, P. E.; Caminada, M., Computational complexity of semi-stable semantics in abstract argumentation frameworks, (Hölldobler, S.; Lutz, C.; Wansing, H., Proceedings of the 11th European Conference on Logics in Artificial Intelligence JELIA 2008. Proceedings of the 11th European Conference on Logics in Artificial Intelligence JELIA 2008, Lecture Notes in Computer Science, vol. 5293 (2008), Springer), 153-165 · Zbl 1178.68557
[18] Dunne, P. E.; Wooldridge, M., Complexity of abstract argumentation, (Simari, G.; Rahwan, I., Argumentation in Artificial Intelligence (2009), Springer US), 85-104
[19] Dvořák, W.; Woltran, S., Complexity of semi-stable and stage semantics in argumentation frameworks, Inform. Process. Lett., 110, 425-430 (2010) · Zbl 1229.68041
[20] Dvořák, W.; Woltran, S., On the intertranslatability of argumentation semantics, J. Artif. Intell. Res., 41, 445-475 (2011) · Zbl 1234.68369
[21] Dvořák, W., Technical note: Exploring \(\Sigma_2^P/\Pi_2^P\)-hardness for argumentation problems with fixed distance to tractable classes, CoRR (2012)
[22] Dvořák, W.; Pichler, R.; Woltran, S., Towards fixed-parameter tractable algorithms for abstract argumentation, Artificial Intelligence, 186, 1-37 (2012) · Zbl 1251.68226
[23] Dvořák, W.; Szeider, S.; Woltran, S., Reasoning in argumentation frameworks of bounded clique-width, (Baroni, P.; Cerutti, F.; Giacomin, M.; Simari, G. R., Computational Models of Argumentation, Proceedings of COMMA 2010. Computational Models of Argumentation, Proceedings of COMMA 2010, Frontiers in Artificial Intelligence and Applications, vol. 216 (2010), IOS), 219-230
[24] J.K. Fichte, S. Szeider, Backdoors to tractable answer-set programming, in: T. Walsh (Ed.), IJCAI, 2011 Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp. 863-868.; J.K. Fichte, S. Szeider, Backdoors to tractable answer-set programming, in: T. Walsh (Ed.), IJCAI, 2011 Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pp. 863-868. · Zbl 1328.68040
[25] Flum, J.; Grohe, M., Parameterized Complexity Theory, Texts in Theoretical Computer Science, An EATCS Series, vol. XIV (2006), Springer-Verlag: Springer-Verlag Berlin
[26] Garey, M. R.; Johnson, D. R., Computers and Intractability (1979), W.H. Freeman and Company: W.H. Freeman and Company New York, San Francisco · Zbl 0411.68039
[27] Gaspers, S.; Szeider, S., Backdoors to satisfaction, CoRR (2011)
[28] Gottlob, G.; Szeider, S., Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems, Comput. J., 51, 303-325 (2006), Survey paper
[29] Jakobovits, H.; Vermeir, D., Robust semantics for argumentation frameworks, J. Logic Comput., 9, 215-261 (1999) · Zbl 0933.68088
[30] Modgil, S.; Caminada, M., Proof theories and algorithms for abstract argumentation frameworks, (Rahwan, I.; Simari, G., Argumentation in Artificial Intelligence (2009), Springer-Verlag), 105-132
[31] Niedermeier, R., Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications (2006), Oxford University Press: Oxford University Press Oxford · Zbl 1095.68038
[32] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley · Zbl 0557.68033
[33] Parsons, S.; Wooldridge, M.; Amgoud, L., Properties and complexity of some formal inter-agent dialogues, J. Logic Comput., 13, 347-376 (2003) · Zbl 1038.03037
[34] Pollock, J. L., How to reason defeasibly, Artificial Intelligence, 57, 1-42 (1992) · Zbl 0763.68056
[35] (Rahwan, I.; Simari, G. R., Argumentation in Artificial Intelligence (2009), Springer Verlag)
[36] Reed, B.; Smith, K.; Vetta, A., Finding odd cycle transversals, Oper. Res. Lett., 32, 299-301 (2004) · Zbl 1052.05061
[37] Robertson, N.; Seymour, P. D.; Thomas, R., Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. (2), 150, 929-975 (1999) · Zbl 0947.05066
[38] Samer, M.; Szeider, S., Backdoor sets of quantified Boolean formulas, J. Automat. Reason., 42, 77-97 (2009) · Zbl 1191.68353
[39] Samer, M.; Szeider, S., Fixed-parameter tractability, (Biere, A.; Heule, M.; van Maaren, H.; Walsh, T., Handbook of Satisfiability (2009), IOS Press), 425-454
[40] B. Verheij, Two approaches to dialectical argumentation: admissible sets and argumentation stages, in: Proceedings of the 8th Dutch Conference on Artificial Intelligence (NAICʼ96), pp. 357-368.; B. Verheij, Two approaches to dialectical argumentation: admissible sets and argumentation stages, in: Proceedings of the 8th Dutch Conference on Artificial Intelligence (NAICʼ96), pp. 357-368.
[41] B. Verheij, A labeling approach to the computation of credulous acceptance in argumentation, in: M.M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 623-628.; B. Verheij, A labeling approach to the computation of credulous acceptance in argumentation, in: M.M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 623-628.
[42] Williams, R.; Gomes, C.; Selman, B., Backdoors to typical case complexity, (Gottlob, G.; Walsh, T., Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003 (2003), Morgan Kaufmann), 1173-1178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.