Lemma 8. There exists an MSO sentence ϕs such that ϕs *is true for* S[**F, x**1] if and only if x1 *is subjectively* accepted in F. Similarly, there exists an MSO sentence ϕo such that ϕo *is true for* S[**F, x**1] if and only if x1 is objectively accepted in F.

In view of Lemmas 7 and 8, Theorem 3 now follows by Courcelle's Theorem.

If both the treewidth of the value graph and the value-width of an value-based system are bounded, then also the extended graph structure has bounded treewidth, hence we have the following corollary.

Corollary 2. *The problems* SUBJECTIVE and OBJECTIVE ACCEPTANCE *can be decided in linear time for valuebased systems for which both value-width and the treewidth of their value graphs are bounded.*
Proof. Let k and k
′ be constants. Let (**T, χ**) be a tree decomposition of the value graph of a value-based system F of width k and assume the value-width of F is k
′. Then (**T, χ**′) with χ
′(t) = Sv∈χ(t)
η
−1(v) is a tree decomposition of the extended graph structure of F. Since |χ
′(t)| ≤ |χ(t)| · k
′ ≤ (k **+ 1)**k
′ holds for all nodes t of T , it follows that the width of (**T, χ**′) is bounded by the constant k
′′ = (k **+ 1)**k
′ − 1. We conclude, in view of Theorem 3, that we can decide both acceptance problems for F in linear time.

## 5 Conclusion

We have studied the computational complexity of persuasive argumentation for value-based argumentation frameworks under structural restrictions. We have established the intractability of deciding subjective or objective acceptance for value-based systems with value-width 2 and attack-width 1, disproving conjectures stated by Dunne.

It might be interesting to note that our reductions show that intractability even holds if the attack relation of the value-based system under consideration forms a directed acyclic graph. On the positive side we have shown that value-based systems with value-width 2 whose graph structure is bipartite are solvable in polynomial time. These results establish a sharp boundary between tractability and intractability of persuasive argumentation for valuebased systems with value-width 2. Furthermore we have introduced the notion of the *extended graph structure* of a value-based system and have shown that subjective and objective acceptance can be decided in linear-time if the treewidth of the extended graph structure is bounded (that is, the problems are *fixed-parameter tractable* when parameterized by the treewidth of the extended graph structure). This is in strong contrast to the intractability of the problems for value-based systems where the treewidth of the graph structure or the treewidth of their value graph is bounded. Therefore we conclude that the extended graph structure seems to be an appropriate graphical model for studying the computational complexity of persuasive argumentation. It might be interesting for future work to extend this study to other graph-theoretic properties or parameters of the extended graph structure.

## References

[1] Jørgen Bang-Jensen and Gregory Gutin. *Digraphs: Theory, Algorithms, Applications*. Springer Monographs in Mathematics. Springer Verlag, London, 2001.

[2] Pietro Baroni and Massimiliano Giacomin. Semantics of abstract argument systems. In Iyad Rahwan and Guillermo Simari, editors, *Argumentation in Artificial Intelligence*, pages 25–44. Springer Verlag, 2009.

[3] T. J. M. Bench-Capon and Paul E. Dunne. Argumentation in artificial intelligence. *Artificial Intelligence*,
171(10-15):619–641, 2007.

[4] Trevor J. M. Bench-Capon. Persuasion in practical argument using value-based argumentation frameworks.

J. Logic Comput., 13(3):429–448, 2003.

[5] Trevor J. M. Bench-Capon, Sylvie Doutre, and Paul E. Dunne. Audiences in argumentation frameworks.

Artificial Intelligence, 171(1):42–71, 2007.

[6] Philippe Besnard and Anthony Hunter. *Elements of Argumentation*. The MIT Press, 2008.