  Logic-based argumentation is a well-established formalism modelling
nonmonotonic reasoning. It has been playing a major role in AI for decades,
now. Informally, a set of formulas is the support for a given claim if it is
consistent, subset-minimal, and implies the claim. In such a case, the pair of
the support and the claim together is called an argument. In this paper, we
study the propositional variants of the following three computational tasks
studied in argumentation: ARG (exists a support for a given claim with respect
to a given set of formulas), ARG-Check (is a given set a support for a given
claim), and ARG-Rel (similarly as ARG plus requiring an additionally given
formula to be contained in the support). ARG-Check is complete for the
complexity class DP, and the other two problems are known to be complete for
the second level of the polynomial hierarchy (Parson et al., J. Log. Comput.,
2003) and, accordingly, are highly intractable. Analyzing the reason for this
intractability, we perform a two-dimensional classification: first, we consider
all possible propositional fragments of the problem within Schaefer's framework
(STOC 1978), and then study different parameterizations for each of the
fragment. We identify a list of reasonable structural parameters (size of the
claim, support, knowledge-base) that are connected to the aforementioned
decision problems. Eventually, we thoroughly draw a fine border of
parameterized intractability for each of the problems showing where the
problems are fixed-parameter tractable and when this exactly stops.
Surprisingly, several cases are of very high intractability (paraNP and
beyond).
