Leibniz Universität Hannover, Institut für Theoretische Informatik,
Germanymahmood@thi.uni-hannover.dehttps://orcid.org/0000-0002-5651-5391
Leibniz Universität Hannover, Institut für Theoretische Informatik,
Germanymeier@thi.uni-hannover.dehttps://orcid.org/0000-0002-8061-5376
Jönköping University, Department of Computer Science and Informatics, School
of Engineering,
Swedenjohannes.schmidt@ju.sehttps://orcid.org/0000-0001-8551-1624 Yasir
Mahmood, Arne Meier, and Johannes Schmidt [100]Theory of computation
Parameterized complexity and exact algorithms [100]Computing methodologies
Knowledge representation and reasoning This work was supported by the German
Research Foundation (DFG), project ME 4279/1-2.

###### Acknowledgements.

The authors thank the anonymous referees for their valuable feedback. John Q.
Open and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016)
CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Parameterized Complexity of Logic-Based Argumentation in Schaefer’s
Framework

Yasir Mahmood  Arne Meier  Johannes Schmidt

###### Abstract

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

###### keywords:

Parameterized complexity, logic-based argumentation, Schaefer’s framework

##  1 Introduction

Argumentation is a nonmonotonic formalism in artificial intelligence around
which an active research community has evolved [2, 1, 32, 3]. Essentially,
there exist two branches of argumentation: the _abstract_ [16] and the _logic-
based_ [4, 5, 9, 31] approach. The abstract setting mainly focusses on
formalizing the argumentative structure in a graph-theoretic way. Arguments
are nodes in a directed graph and the ‘attack-relation’ draws which argument
eliminates which other. In the logic-based method, one looks for inclusion-
minimal consistent sets of formulas $\Phi$ (the _support_) that entail a
_claim_ $\alpha$, modelled through a formula (in the positive case one calls
$(\Phi,\alpha)$ an _argument_). In this paper, we focus on the latter
formalism and, specifically, study three decision problems. The first,
$\mathrm{ARG}$, asks, given a set of formulas $\Delta$ (the _knowledge-base_)
and a formula $\alpha$, whether there exists a subset $\Phi\subseteq\Delta$
such that $(\Phi,\alpha)$ is an argument in $\Delta$. The two further problems
of interest are $\mathrm{ARG\text{-}Check}$ (is a given set a support for a
given claim), and $\mathrm{ARG\text{-}Rel}$ ($\mathrm{ARG}$ plus requiring an
additionally given formula to be contained in the support, too).

######  Example 1.1 ([4]).

Consider the following two arguments. (A1) Support: Donald is a public person,
so we can publicize details about his private life. Claim: We can publicize
that Donald plays golf. (A2) Support: Donald just resigned from politics; as a
result, he is no longer a public person. Claim: Donald is no longer a public
person.

Formalizing these arguments would yield $A_{1}:\Phi_{1}=\\{x_{pd}\to
x_{dg},x_{pd}\\},\alpha_{1}=\\{x_{dg}\\}$, $A_{2}:\Phi_{2}=\\{x_{rd}\to\lnot
x_{pd},x_{rd}\\},\alpha_{2}=\\{\lnot x_{pd}\\}$, where $x_{pd}\triangleq$
“Donald is a public person”, $x_{dg}\triangleq$“Donald plays golf”,
$x_{rd}\triangleq$“Donald resigned from politics”. Each argument is supporting
its claim, yet together they are conflicting, as $A_{2}$ attacks $A_{1}$.

It is rather computationally involved to compute the support of an argument,
as $\mathrm{ARG}$ was shown to be $\mathbf{\Sigma_{2}^{P}}$-complete by
Parsons et al. [29]. Yet, there have been made efforts to improve the
understanding of this high intractability by Creignou et al. [10, 14] in two
settings: Schaefer’s [34] as well as Post’s [30] framework. Clearly, such
research aims for drawing the fine intractability frontier of computationally
involved problems to show for what restrictions there still is hope to reach
algorithms running for practical applications. Both approaches mainly focus on
restrictions on the logical part of the problem language, that is, restricting
the allowed connectives or available constraints.

In this paper, Schaefer’s approach is our focus, that is, the formulas we
study are propositional formulas in conjunctive normalform (CNF) whose clauses
are formed depending on a fixed set of relations $\Gamma$ (the so-called
_constraint language_ , short CL). In this setting, Schaefer’s framework [34]
captures well-known classes of CNF-formulas (e.g., Horn, dual-Horn, or Krom).
Accordingly, one can see classifications in such a setting as a one-
dimensional approach (the dimension is given rise by the considered logical
fragments).

We consider a second dimension on the problem in this paper, namely, by
investigating its parameterized complexity [15]. Motivated by the claim that
the input length is not the only important structural aspect of problems, one
studies so-called parameterizations (or parameters) of a problem. The goal of
such studies is to identify a parameter that is relevant for practice but also
is slowly growing or even of constant value. If, additionally, one is able to
construct an algorithm that solves the problem in time $f(k)\cdot|x|^{O(1)}$
for some computable function $f$ and all inputs $(x,k)$, then one calls the
problem _fixed-parameter tractable_. That is why in this case one can solve
the problem (for fixed parameter values) in polynomial time. As a result, this
complexity class is seen to capture the idea of efficiency in the
parameterized sense. While $\mathbf{NP}$-complete problems are considered
intractable in the classical setting, on the parameterized level, the
complexity class $\mathbf{W}[1]$ is seen to play this counterpart. Informally,
this class is characterized via a special kind of satisfiability questions.
Above this class an infinite $\mathbf{W}$-hierarchy is defined which
culminates in the class $\mathbf{W}[\mathbf{P}]$, which in turn is contained
in the class $\mathbf{para\text{-}}\mathbf{NP}$ (problems solvable by NTMs in
time $f(k)\cdot|x|^{O(1)}$).

#### Contributions

Our main contributions are the following.

  1. 1.

We initiate a thorough study of the parameterized complexity of logic-based
argumentation. We study three parameters: size of the support, of the claim,
and of the knowledge-base. We show that the complexity of $\mathrm{ARG}$,
regarding the claim as a parameter, varies: $\mathbf{FPT}$, $\mathbf{W}[1]$-,
$\mathbf{W}[2]$-, $\mathbf{para\text{-}}\mathbf{NP}$-,
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-, as well as
$\mathbf{para\text{-}}\mathbf{\Sigma_{2}^{P}}$-complete cases. For the same
parameter, $\mathrm{ARG\text{-}Check}$ is $\mathbf{FPT}$ for Schaefer,
$\mathbf{para\text{-}}\mathbf{DP}$-complete otherwise.
$\mathrm{ARG\text{-}Rel}$ is $\mathbf{FPT}$,
$\mathbf{para\text{-}}\mathbf{NP}$-, or
$\mathbf{para\text{-}}\mathbf{\Sigma_{2}^{P}}$-complete.

The size of the knowledge-base as the parameter yields dichotomy results for
the two problems $\mathrm{ARG}$ and $\mathrm{ARG\text{-}Rel}$: $\mathbf{FPT}$
versus membership in $\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$ and a lower
bound that relates to the implication problem.

Concerning the size of the support as the parameter, we prove a dichotomy:
$\mathbf{FPT}$ versus $\mathbf{para\text{-}}\mathbf{DP}$-membership and the
same hardness as the implication problem.

  2. 2.

As a byproduct, we advance the algebraic tools in the context of Schaefer’s
framework, and show a list of technical implementation results that are
independent of the studied problem and might be beneficial for further
research in the constraint context.

  3. 3.

We classify the parameterized complexity of the implication problem (does a
set of propositional formulas $\Phi$ imply a propositional formula $\alpha$?)
with respect to the parameter $|\alpha|$ and show that it is $\mathbf{FPT}$ if
the CL is Schaefer, and $\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-complete
otherwise.

#### Related Work

Very recently, Mahmood et al. [26] presented a parameterized classification of
abductive reasoning in Schaefer’s framework. Some of their cases, as well as
results from Nordh and Zanuttini [28] relate to some of our results. The
studies of the implication problem in the frameworks of Schaefer [35] as well
as in the one in Post [6] prove a classical complexity landscape. Last year,
Hecher et al. [18] conducted a parameterized study of abstract argumentation.
The known classical results [10, 28, 35, 6] are partially used in some of our
proofs, e.g., showing some parameterized complexity lower bounds. The two
mentioned parameterized complexity related papers [18, 26] both are about
different formalisms that are slightly related to our setting (the first is
about abstract argumentation, the second on abduction).

##  2 Preliminaries

We assume familiarity with basic notions in complexity theory (cf. [36]) and
use the complexity classes
$\mathbf{P},\mathbf{NP},\mathbf{co}\mathbf{NP},\mathbf{\Sigma_{2}^{P}}$. For a
set $S$, we write $|S|$ for its _cardinality_. Abusing notation, we will use
$|w|$, for a string $w$, to denote its _length_. If $\varphi$ is a formula,
then $\mathrm{Vars}(\varphi)$ denotes its set of variables, and
$\mathrm{enc}(\varphi)$ its _encoding_. W.l.o.g., we assume a reasonable
encoding computable in polynomial time that encodes variables in binary. The
_weight_ of an assignment $\sigma$ is the number of variables mapped to $1$.

#### Parameterized Complexity

We give a brief introduction to parameterized complexity theory. A more
detailed exposition can be found in the textbook of Downey and Fellows ([15]).
A _parameterized problem (PP)_ $\Pi$ is a subset of
$\Sigma^{*}\times\mathbb{N}$, where $\Sigma$ is an alphabet. For an instance
$(x,k)\in\Sigma^{*}\times\mathbb{N}$, $k$ is called the _parameter_. If there
exists a deterministic algorithm deciding $\Pi$ in time $f(k)\cdot|x|^{O(1)}$
for every input $(x,k)$, where $f$ is a computable function, then $\Pi$ is
_fixed-parameter tractable_ (short: $\mathbf{FPT}$).

######  Definition 2.1.

Let $\Sigma$ and $\Delta$ be two alphabets. A PP
$\Pi\subseteq\Sigma^{*}\times\mathbb{N}$ _fpt-reduces_ to a PP
$\Theta\subseteq\Delta^{*}\times\mathbb{N}$, in symbols
$\Pi\leq^{\mathrm{\mathbf{FPT}}}\Theta$, if the following is true: (i) there
is an $\mathbf{FPT}$-computable function $f$, such that, for all
$(x,k)\in\Sigma^{*}\times\mathbb{N}$: $(x,k)\in\Pi\Leftrightarrow
f(x,k)\in\Theta$, (ii) there exists a computable function
$g\colon\mathbb{N}\to\mathbb{N}$ such that for all
$(x,k)\in\Sigma^{*}\times\mathbb{N}$ and $f(x,k)=(y,\ell)$: $\ell\leq g(k)$.

The problems $\Pi$ and $\Theta$ are $\mathbf{FPT}$-equivalent if both
$\Pi\leq^{\mathrm{\mathbf{FPT}}}\Theta$ and
$\Theta\leq^{\mathrm{\mathbf{FPT}}}\Pi$ is true. We also use higher classes
via the concept of _precomputation on the parameter_.

######  Definition 2.2.

Let $\mathcal{C}$ be any complexity class. Then
$\mathbf{para\text{-}}\mathcal{C}$ is the class of all PPs
$\Pi\subseteq\Sigma^{*}\times\mathbb{N}$ such that there exists a computable
function $\pi\colon\mathbb{N}\to\Delta^{*}$ and a language $L\in\mathcal{C}$
with $L\subseteq\Sigma^{*}\times\Delta^{*}$ such that for all
$(x,k)\in\Sigma^{*}\times\mathbb{N}$ we have that
$(x,k)\in\Pi\Leftrightarrow(x,\pi(k))\in L$.

Observe that $\mathbf{para\text{-}}\mathbf{P}=\mathbf{FPT}$ is true. For a
constant $c\in\mathbb{N}$ and a PP $\Pi\subseteq\Sigma^{*}\times\mathbb{N}$,
the _$c$ -slice of $\Pi$_, written as $\Pi_{c}$, is defined as
$\Pi_{c}:=\\{\,(x,k)\in\Sigma^{*}\times\mathbb{N}\mid k=c\,\\}$. Observe that,
in our setting, showing $\Pi\in\mathbf{para\text{-}}\mathcal{C}$, it suffices
to show $\Pi_{c}\in\mathcal{C}$ for every $c\in\mathbb{N}$. Consider the
following special subclasses of formulas:

$\begin{array}[]{@{}r@{\,}c@{\,}l@{}}\Gamma_{0,d}&=&\\{\,\ell_{1}\land\ldots\land\ell_{c}\mid\ell_{1},\ldots,\ell_{c}\text{
are literals and }c\leq d\,\\},\\\
\Delta_{0,d}&=&\\{\,\ell_{1}\lor\ldots\lor\ell_{c}\mid\ell_{1},\ldots,\ell_{c}\text{
are literals and }c\leq d\,\\},\\\
\Gamma_{t,d}&=&\left\\{\,\bigwedge\limits_{i\in
I}\alpha_{i}\,\middle|\,\alpha_{i}\in\Delta_{t-1,d}\text{ for }i\in
I\,\right\\},\\\ \Delta_{t,d}&=&\left\\{\,\bigvee\limits_{i\in
I}\alpha_{i}\,\middle|\,\alpha_{i}\in\Gamma_{t-1,d},\text{ }i\in
I\,\right\\}.\end{array}$

The parameterized weighted satisfiability problem
($\mathrm{p\text{-}}\mathrm{WSAT}$) for propositional formulas is defined as
below. The problem $\mathrm{p\text{-}}\mathrm{WSAT}(\Gamma_{t,d})$ asks, given
a $\Gamma_{t,d}$-formula $\alpha$ with $t,d\geq 1$ and $k\in\mathbb{N}$,
parameterized by $k$, is there a satisfying assignment for $\alpha$ of weight
$k$?

The classes of the $\mathbf{W}$-hierarchy can be defined in terms of these
problems.

######  Proposition 2.3 ([15]).

The problem $\mathrm{p\text{-}}\mathrm{WSAT}(\Gamma_{t,d})$ is
$\mathbf{W}[t]$-complete for each $t\geq 1$ and $d\geq 1$, under
$\leq^{\mathrm{\mathbf{FPT}}}$-reductions.

#### Logic-based Argumentation

All formulas in this paper are propositional formulas. We follow the notion of
Creignou et al. [10].

######  Definition 2.4 ([4]).

Given a set of formulas $\Phi$ and a formula $\alpha$, one says that
$(\Phi,\alpha)$ is an _argument (for $\alpha$)_ if (1) $\Phi$ is consistent,
(2) $\Phi\models\alpha$, and (3) $\Phi$ is subset-minimal w.r.t. (2). In case
of $\Phi\subseteq\Delta$, $(\Phi,\alpha)$ is an _argument in $\Delta$_. We
call $\alpha$ the _claim_ , $\Phi$ the _support_ of the argument, and $\Delta$
the _knowledge-base_.

In this paper, we consider three problems from the area of logic-based
argumentation, namely $\mathrm{ARG}$, $\mathrm{ARG\text{-}Check}$, and
$\mathrm{ARG\text{-}Rel}$. The problem $\mathrm{ARG}$ asks, given a set of
formulas $\Delta$ and a formula $\alpha$, is there a set $\Phi\subseteq\Delta$
such that $(\Phi,\alpha)$ is an argument in $\Delta$? The problem
$\mathrm{ARG\text{-}Check}$ asks, given a set of formulas $\Phi$ and a formula
$\alpha$, is $(\Phi,\alpha)$ an argument? The problem
$\mathrm{ARG\text{-}Rel}$ asks, given a set of formulas $\Delta$, and formulas
$\psi\in\Delta$ and $\alpha$, is there a set $\Phi\subseteq\Delta$ with
$\psi\in\Phi$ such that $(\Phi,\alpha)$ is an argument in $\Delta$?

Turning to the parameterized complexity perspective on the introduced
problems, immediate parameters that we consider are
$|\mathrm{enc}(\mathcal{X})|$ (size of the encoding of $\mathcal{X}$),
$|\mathcal{X}|$ (number of formulas in $\mathcal{X}$),
$|\mathrm{Vars}(\mathcal{X})|$ (number of variables in $\mathcal{X}$) for
$\mathcal{X}\in\\{\Delta,\Phi\\}$, as well as $|\mathrm{enc}(\alpha)|$ and
$|\mathrm{Vars}(\alpha)|$. Regarding the parameterized versions of the
problems from above, e.g., $\mathrm{p\text{-}}\mathrm{ARG}(k)$, where $k$ is a
parameter, then defines the version of $\mathrm{ARG}$ parameterized by $k$,
accordingly.

In the following, we want to formally relate the mentioned notions of encoding
length, number of variables, as well as number of formulas. We will see that
bounding the encoding length, implies having limited space for encoding
variables and, in turn, restricts the number of possible formulas. However,
the converse is also true: if one bounds the number of variables, then one
also has limited possibilities about defining _different_ formulas. The
following definition makes clear what ‘different’ means in our context.

######  Definition 2.5 (Formula redundancy).

A CNF-formula $\varphi=\bigwedge_{i=1}^{m}C_{i}$, with
$C_{i}=(\ell_{i,1}\lor\cdots\lor\ell_{i,n_{i}})$ is _redundant_ if there exist
$1\leq i\neq j\leq m$ such that $\\{\,\ell_{i,k}\mid 1\leq k\leq
n_{i}\,\\}=\\{\,\ell_{j,k}\mid 1\leq k\leq n_{j}\,\\}$.

######  Example 2.6.

The formulas $x\land x$ and $(x\lor x\lor y)\land(x\lor y)$ are redundant. The
formulas $x\land y$ and $(x\lor y)\land x$ are not redundant.

Liberatore [24] studied a stronger notion of redundancy in the context of CNF-
formulas, namely, on the level of implied clauses. We do not need such a
strict notion of redundancy here, as the weaker notion suffices for proving
the following Lemma. As a result, in the following, we consider only formulas
that are just not redundant. The redundancy (in our context) can be
straightforwardly checked in time quadratic in the length of the given
formula.

######  Lemma 2.7.

For any set of CNF-formulas $\Phi$, we have that

  1. 1.

$|\Phi|\leq 2^{2^{2\cdot|\mathrm{Vars}(\Phi)|}}$,

  2. 2.

$f(|\mathrm{Vars}(\Phi)|)\leq|\mathrm{enc}(\Phi)|$, where $f$ is some
computable function, and

  3. 3.

$|\mathrm{enc}(\Phi)|\leq{|\Phi|}^{3}$.

######  Proof 2.8.

  1. 1.

Let $v\in\mathbb{N}$ be a fixed number of variables. As we consider CNF-
formulas, a formula consists of clauses of literals. The number of possible
clauses then is the number of subsets of possible literals
$\\{x_{1},\dots,x_{v},\lnot x_{1},\dots,\lnot x_{v}\\}$, that is, $2^{2\cdot
v}$-many. A CNF-formula is a subset of the set of possible clauses. As a
result, we have $2^{2^{2\cdot v}}$-many possible CNF-formulas.

  2. 2.

We represent a variable $x_{i}$ by its binary encoding. Clearly,
$|\mathrm{enc}(\Phi)|=\sum_{\varphi\in\Phi}|\mathrm{enc}(\varphi)|$. However,

$\displaystyle|\mathrm{enc}(\varphi)|$
$\displaystyle\leq|\varphi|\cdot\log(|\mathrm{Vars}(\varphi)|)+|\varphi|$
$\displaystyle=|\varphi|\cdot(\log(|\mathrm{Vars}(\varphi)|)+1)$
$\displaystyle\leq|\Phi|\cdot(\log(|\mathrm{Vars}(\Phi)|)+1).$

As a result, we get

$\displaystyle|\mathrm{enc}(\Phi)|$
$\displaystyle\leq|\Phi|\cdot\max_{\varphi\in\Phi}|\mathrm{enc}(\varphi)|$
$\displaystyle\leq|\Phi|^{2}\cdot(\log(|\mathrm{Vars}(\Phi)|)+1)$ As
$|\Phi|\leq|\mathrm{enc}(\Phi)|$ is true, we have that
$\displaystyle|\mathrm{enc}(\Phi)|$
$\displaystyle\leq|\mathrm{enc}(\Phi)|^{2}\cdot(\log(|\mathrm{Vars}(\Phi)|)+1)$
$\displaystyle\Leftrightarrow(\log(|\mathrm{Vars}(\Phi)|)+1)^{-1}$
$\displaystyle\leq|\mathrm{enc}(\Phi)|$

  3. 3.

As we only consider formulas that are not redundant, the encoding length of a
set of formulas contains information about the number of its formulas. We have
that $|\mathrm{enc}(\Phi)|\leq|\Phi|^{2}\cdot(\log(|\mathrm{Vars}(\Phi)|)+1)$
(as in (2.)). However, $|\Phi|\leq 2^{2^{2\cdot|\mathrm{Vars}(\Phi)|}}$, and,
as a result, we get

$|\mathrm{enc}(\Phi)|\leq|\Phi|^{2}\cdot(\log(\log(2\cdot|\Phi|))+1)\leq|\Phi|^{3}.$

Notice that due to Lemma 2.7, the problems $\mathrm{ARG}$,
$\mathrm{ARG\text{-}Check}$, $\mathrm{ARG\text{-}Rel}$ parameterized with
respect to any of the parameters for the respective three (two) variants
introduced above are $\mathbf{FPT}$-equivalent. As a result, we will choose
the one of the three (two) variants in our results that is technically most
convenient. Notice also that the parameter $|\Phi|$ only makes sense for
$\mathrm{ARG\text{-}Check}$, whereas $|\Delta|$ makes sense only for the other
two problems, that is, $\mathrm{ARG}$ and $\mathrm{ARG\text{-}Rel}$.

###  2.1 Schaefer’s Framework

For a deeper introduction into Schaefer’s CSP framework, consider the article
of Böhler et al. [8].

A _logical relation_ of arity $k\in\mathbb{N}$ is a relation
$R\subseteq\\{0,1\\}^{k}$, and a _constraint_ $C$ is a formula
$C=R(x_{1},\dots,x_{k})$, where $R$ is a $k$-ary logical relation, and
$x_{1},\dots,x_{k}$ are (not necessarily distinct) variables. If $V$ is a set
of variables and $u$ a variable, then $C[V/u]$ denotes the constraint obtained
from $C$ by replacing every occurrence of every variable of $V$ by $u$. An
assignment $\theta$ _satisfies $C$_, if
$(\theta(x_{1}),\dots,\theta(x_{k}))\in R$. A _constraint language_ (CL)
$\Gamma$ is a finite set of logical relations, and a _$\Gamma$ -formula_ is a
conjunction of constraints over elements from $\Gamma$. Eventually, a
$\Gamma$-formula $\varphi$ is _satisfied_ by an assignment $\theta$, if
$\theta$ simultaneously satisfies all constraints in it. In such a case
$\theta$ is also called a _model of $\varphi$_. Whenever a $\Gamma$-formula or
a constraint is logically equivalent to a single clause or term or literal, we
treat it as such. We say that a $k$-ary relation $R$ is represented by a
formula $\phi$ in CNF if $\phi$ is a formula over $k$ distinct variables
$x_{1},\ldots,x_{k}$ and $\phi\equiv R(x_{1},\ldots,x_{k})$. Moreover, we say
that $R$ is

  * •

_Horn_ (resp., _dual-Horn_) if $\phi$ contains at most one positive (negative)
literal per each clause.

  * •

_Bijunctive_ if $\phi$ contains at most two literals per each clause.

  * •

_Affine_ if $\phi$ is a conjunction of linear equations of the form
$x_{1}\oplus\ldots\oplus x_{n}=a$ where $a\in\\{0,1\\}$.

  * •

_Essentially negative_ if every clause in $\phi$ is either negative or unit
positive. $R$ is _essentially positive_ if every clause in $\phi$ is either
positive or unit negative.

  * •

_$1$ -valid_ (resp., _$0$ -valid_) if every clause in $\phi$ contains at least
one positive (negative) literal.

Furthermore, we say a relation is _Schaefer_ if it is Horn, dual-Horn,
bijunctive, or affine. We say that a relation is _$\varepsilon$ -valid_ if it
is $1$\- or $0$-valid or both. Finally, for a property _P_ of a relation, we
say that a CL $\Gamma$ is _P_ if all relations in $\Gamma$ are _P_.

######  Definition 2.9.

  1. 1.

The set $\left\langle\Gamma\right\rangle$ is the smallest set of relations
that contains $\Gamma$, the equality constraint, $=$, and which is closed
under primitive positive first order definitions, that is, if $\phi$ is an
$\Gamma\cup\\{=\\}$-formula and $R(x_{1},\dots,x_{n})\equiv\exists
y_{1}\dots\exists y_{l}\phi(x_{1},\dots,x_{n},y_{1},\dots,y_{l})$, then
$R\in\left\langle\Gamma\right\rangle$. In other words,
$\left\langle\Gamma\right\rangle$ is the set of relations that can be
expressed as a $\Gamma\cup\\{=\\}$-formula with existentially quantified
variables.

  2. 2.

The set $\left\langle\Gamma\right\rangle_{\neq}$ is the set of relations that
can be expressed as a $\Gamma$-formula with existentially quantified variables
(no equality relation is allowed).

  3. 3.

The set $\left\langle\Gamma\right\rangle_{\not\exists,\neq}$ is the set of
relations that can be expressed as a $\Gamma$-formula (neither the equality
relation nor existentially quantified variables are allowed).

The set $\left\langle\Gamma\right\rangle$ is called a _relational clone_ or a
_co-clone_ with _base_ $\Gamma$ [7]. Notice that for a co-clone $\mathsf{C}$
and a CL $\Gamma$ the statements $\Gamma\subseteq\mathsf{C}$,
$\left\langle\Gamma\right\rangle\subseteq\mathsf{C}$,
$\left\langle\Gamma\right\rangle_{\neq}\subseteq\mathsf{C}$ and
$\left\langle\Gamma\right\rangle_{\not\exists,\neq}\subseteq\mathsf{C}$ are
equivalent. Throughout the paper, we refer to different types of Boolean
relations and corresponding co-clones following Schaefer’s terminology [34].
For a tabular overview of co-clones, relational properties, and bases, we
refer the reader to Table 1. Note that
$\left\langle\Gamma\right\rangle_{\neq}\subseteq\left\langle\Gamma\right\rangle$
is true by definition. The other direction is not true in general. However, if
$(x=y)\in\left\langle\Gamma\right\rangle_{\neq}$, then we have that
$\left\langle\Gamma\right\rangle_{\neq}=\left\langle\Gamma\right\rangle$.

######  Example 2.10.

Table 1: Overview of bases [7] and clause descriptions [28] for co-clones,
where EVEN4 = $x_{1}\oplus x_{2}\oplus x_{3}\oplus x_{4}\oplus 1$.

Let $R(x_{1},x_{2},x_{3})\mathrel{\mathop{:}}=(x_{1}\lor x_{2}\lor
x_{3})\land(\neg x_{1}\lor\neg x_{2}\lor\neg x_{3})$. Then

${(x_{1}\lor x_{2})\land(x_{2}\oplus x_{3}=0)}\equiv\exists
y(R(x_{1},x_{2},y)\land F(y)\land(x_{2}=x_{3})),$

where $F=\\{0\\}$. This implies that $(x_{1}\lor x_{2})\land(x_{2}\oplus
x_{3}=0)\in\left\langle\\{\,R,F\,\\}\right\rangle$.

###  2.2 Technical Implementation Results

We say a Boolean relation $R$ is _strictly essentially positive_ (resp.,
_strictly essentially negative_) if it can be defined by a conjunction of
literals and positive clauses (resp., negative clauses) only. Note that the
only difference to essentially positive (resp., essentially negative) is the
absence of the equality relation (see Table 1). We abbreviate in the following
essentially positive by “ess.pos.” and essentially negative by “ess.neg.”.

######  Proposition 2.11.

[26, Lem. 7]] Let $\Gamma$ be a CL that is neither ess.pos., nor ess.neg.
Then, we have that $(x=y)\in\left\langle\Gamma\right\rangle_{\neq}$ and
$\left\langle\Gamma\right\rangle=\left\langle\Gamma\right\rangle_{\neq}$.

With the following implementation result we can strengthen this statement to
Lemma 2.14.

######  Lemma 2.12.

Let $\Gamma$ be a CL that is not $\varepsilon$-valid. If $\Gamma$ is ess.neg.
and not strictly ess.neg. or ess.pos. and not strictly ess.pos. then we have
that $(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$.

######  Proof 2.13.

We prove the statement for $\Gamma$ that is ess.pos. but not strictly ess.pos.
The other case can be treated analogously. W.l.o.g., let $\Gamma=\\{R\\}$,
thus $R$ is ess.pos. but not strictly ess.pos. Furthermore, $R$ is neither
1-valid nor 0-valid. Let $R$ be of arity $k$ and let
$V=\\{x_{1},\dots,x_{k}\\}$ be a set of $k$ distinct variables. By definition
of ess.pos. (cf. $\mathsf{IS}_{02}$ in Table 1), $R$ can be written as
conjunction of negative literals, positive clauses and equalities.

If $R$ can be written without any equality, then $R$ is strictly ess.pos., a
contradiction. As a result, any representation of $R$ as conjunction of
negative literals, positive clauses and equalities requires at least one
equality. Suppose, w.l.o.g., that $R(x_{1},\dots,x_{k})\models(x_{1}=x_{2})$,
while $R(x_{1},\dots,x_{k})\not\models x_{1}$ and
$R(x_{1},\dots,x_{k})\not\models\neg x_{1}$. We define the following three
subsets of $V$: $W=\\{\,x_{i}\mid
R(x_{1},\dots,x_{k})\models(x_{1}=x_{i})\,\\}$, $N=\\{\,x_{i}\mid
R(x_{1},\dots,x_{k})\models\neg x_{i}\,\\}$, and $P=V\setminus(W\cup N)$

By construction the three sets provide a partition of $V$. Then, $W$ is
nonempty by construction, $N$ is nonempty since $R$ is not 1-valid and $P$ is
nonempty since $R$ is not 0-valid. Denote by $C$ the $\\{R\\}$-constraint
$C=R(x_{1},\dots,x_{k})$. Consider the constraint
$M(x_{1},x_{2},t,f)=C[W/x_{2},P/t,N/f]$. One verifies that
$M(x_{1},x_{2},t,f)\equiv(x_{1}=x_{2})\land t\land\neg f$.

######  Lemma 2.14.

Let $\Gamma$ be a CL that is neither strictly ess.pos., nor strictly ess.neg.
Then $(x=y)\in\left\langle\Gamma\right\rangle_{\neq}$ and
$\left\langle\Gamma\right\rangle=\left\langle\Gamma\right\rangle_{\neq}$.

######  Proof 2.15.

If $\Gamma$ is not ess.pos. and not ess.neg. the statement follows from
Proposition 2.11. Note that this lemma’s statement implies that $\Gamma$ is
not $\varepsilon$-valid. If $\Gamma$ is ess.pos. or ess.neg., by Lemma 2.12 we
have $(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. Conclude by noticing
that $(x=y)\equiv\exists t\exists f\,(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\neq}$.

######  Lemma 2.16.

Let $\Gamma$ be a CL that is neither $\varepsilon$-valid, nor ess.pos., nor
ess.neg. Then, if $\Gamma$ is

  1. 1.

not Horn, not dual-Horn, and not complementive, then $(x\neq y)\land
t\land\neg f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$,

  2. 2.

not Horn, not dual-Horn, and complementive, then $(x\neq
y)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$, and

  3. 3.

Horn or dual-Horn, then $(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$.

######  Proof 2.17.

This follows immediately from the proof of Proposition 2.11. The proof given
in [26, 25, Lemma 7] makes a case distinction according to whether $\Gamma$ is
0-valid and/or 1-valid. In the case of non $\varepsilon$-valid $\Gamma$ a
further case distinction is made according to whether $\Gamma$ is Horn and/or
dualHorn. Here the statements 1., 2., and 3. are proven.

Let us denote by $\mathrm{T}/\mathrm{F}$ the unary relations that implement
true/false. That is, $\mathrm{T}=\\{(1)\\}$ and $\mathrm{F}=\\{(0)\\}$. The
following implementation results are folklore.

######  Proposition 2.18 (Creignou et al. [11]).

If $\Gamma$ is a CL that is

  1. 1.

complementive and not $\varepsilon$-valid, then $(x\neq
y)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$,

  2. 2.

neither complementive, nor $\varepsilon$-valid, then
$(t\land\bar{f})\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$.

  3. 3.

$1$-valid and not $0$-valid, then
$\mathrm{T}\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$,

  4. 4.

$0$-valid and not $1$-valid, then
$\mathrm{F}\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$, and

  5. 5.

$0$-valid and $1$-valid, then
$(x=y)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$.

###  2.3 Parameterized Implication Problem

In this subsection, we consider the parameterized complexity of the
implication problem ($\mathrm{IMP}$). The problem $\mathrm{IMP}(\Gamma)$ asks,
given a set of $\Gamma$-formulas $\Phi$ and a $\Gamma$-formula $\alpha$, is
$\Phi\models\alpha$ true? For $\mathrm{p\text{-}}\mathrm{IMP}$, the
parameterized version of $\mathrm{IMP}$, we consider the parameter
$k\in\\{|\Phi|,|\alpha|\\}$, and also write
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,k)$. The following corollary is due to
Schnoor and Schnoor [35, Theorem 6.5]. They study a restriction of our problem
$\mathrm{IMP}$, where $|\Phi|=1$.

######  Corollary 2.19.

Let $\Gamma$ be a CL. $\mathrm{IMP}(\Gamma)$ is in $\mathbf{P}$ when $\Gamma$
is Schaefer and $\mathbf{co}\mathbf{NP}$-complete otherwise.

Consequently, the parameterized problem
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,k)$ is $\mathbf{FPT}$ when $\Gamma$ is
Schaefer and $k\in\\{|\Phi|,|\alpha|\\}$. We consider the cases when $\Gamma$
is not Schaefer. In the following, we differentiate the restrictions on $\Phi$
from the ones on $\alpha$. That is, we introduce a technical variant,
$\mathrm{IMP}(\Gamma^{\prime},\Gamma)$ of the implication problem. An instance
of $\mathrm{IMP}{(\Gamma^{\prime},\Gamma)}$ is a tuple $(\Phi,\alpha)$, where
$\Phi$ is a set of $\Gamma^{\prime}$-formulas and $\alpha$ is a
$\Gamma$-formula. The following corollary also follows from the work of
Schnoor and Schnoor [35, Theorem 6.5].

######  Corollary 2.20.

Let $\Gamma$ and $\Gamma^{\prime}$ be non-Schaefer CLs. If
$\Gamma^{\prime}\subseteq\left\langle\Gamma\right\rangle$ then
$\mathrm{IMP}(\Gamma^{\prime},\Gamma)\leq^{\mathrm{\mathbf{P}}}_{m}\mathrm{IMP}(\Gamma)$.

Regarding non-Schaefer CLs, it turns out that the parameter $\alpha$ does not
make the problem any easier. One possible explanation for this hardness is
that the formulas in $\Phi$ and $\alpha$ do not necessarily share a set of
variables.

######  Lemma 2.21.

The problem $\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-complete when the CL $\Gamma$ is
not Schaefer.

######  Proof 2.22.

Membership follows because the classical problem is in
$\mathbf{co}\mathbf{NP}$. To achieve the lower bound, we reduce from the
unsatisfiability problem. That is, given a formula $\Phi$, the question is
whether $\Phi$ is unsatisfiable. Moreover, checking unsatisfiability is
$\mathbf{co}\mathbf{NP}$-complete for non-Schaefer languages (follows by
Schaefer’s [34] $\mathrm{SAT}$ classification).

We will inherently use Corollary 2.20 and make a case distinction as whether
$(\Phi,\alpha)$ is $1$-valid, $0$-valid or complementive.

Case 1.

Let $\Gamma$ be $1$-valid and not $0$-valid. We prove that for some well
chosen $1$-valid language $\Gamma^{\prime}$ and a $\Gamma^{\prime}$-formula
$\Phi$, the problem
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma^{\prime},\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-hard. According to item (3.) in
Proposition 2.18,
$\mathrm{T}\in\left\langle\Gamma^{\prime}\right\rangle_{\not\exists,\neq}$.
Let $\alpha=\mathrm{T}(x)$ and $\Phi$ be a $\Gamma^{\prime}$-formula where $x$
does not appear. Then $\Phi\models\alpha$ if and only if $\Phi$ is
unsatisfiable. This is because, if $\Phi$ is satisfiable then there is an
assignment $s$ such that $s\models\psi$. This gives a contradiction because
the assignment $s^{\prime}$ that extends $s$ by $s^{\prime}(x)=0$ satisfies
that $s^{\prime}\models\Phi$ and $s^{\prime}\not\models\alpha$.

Case 2.

Let $\Gamma$ be $0$-valid and not $1$-valid. According to item (4.) in
Proposition 2.18,
$\mathrm{F}\in\left\langle\Gamma^{\prime}\right\rangle_{\not\exists,\neq}$.
This case is similar to Case 1, as we take $\alpha=\mathrm{F}(x)$ and $\Phi$ a
$\Gamma^{\prime}$-formula not containing $x$.

Case 3.

Let $\Gamma$ be complementive but not $\varepsilon$-valid. We prove that for
some well chosen complementive language $\Gamma^{\prime}$ and a
$\Gamma$-formula $\alpha$, the problem
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma^{\prime},\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-hard. According to item (1.) in
Proposition 2.18,
$x\not=y\in\left\langle\Gamma^{\prime}\right\rangle_{\not\exists,\neq}$. Then,
$\mathbf{co}\mathbf{NP}$-hardness follows, as for any set of
$\Gamma^{\prime}$-formulas $\Phi$, $\Phi\models(x\neq x)$ if and only if
$\Phi$ is unsatisfiable.

Case 4.

Let $\Gamma$ be $0$\- and $1$-valid. By Lemma 2.16 (1.)/(2.), we have access
to ‘$\neq$’. We can state a reduction from the complement of $\mathrm{SAT}$ to
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\alpha|)$ as in Case 3. That is,
$\Phi$ is unsatisfiable if and only if $\Phi\models x\neq x$ for a fresh
variable $x$.

Note that regarding the parameter $|\Phi|$, the problem
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\Phi|)$ is $\mathbf{FPT}$ if $\Gamma$
is Schaefer. Otherwise, only $\mathbf{co}\mathbf{NP}$-membership is clear.

##  3 Parameter: Size of the Claim $\alpha$

In this section we discuss the complexity results regarding the parameter
$\alpha$, that is, the number of variables and the encoding size of $\alpha$.
It turns out that the computational complexity of the argumentation problems
is hidden in the structure of the underlying CL. That is, in many cases,
considering the claim size as a parameter does not lower the complexity. This
is proved by noting that certain slices of the parameterized problems already
yield hardness results.

######  Theorem 3.1.

$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$, for a CL $\Gamma$, is

  1. 1.

$\mathbf{FPT}$ if $\Gamma$ is Schaefer and $\varepsilon$-valid,

  2. 2.

$\mathbf{para\text{-}}\mathbf{NP}$-complete if $\Gamma$ is Schaefer and
neither $\varepsilon$-valid, nor strictly ess.pos., nor strictly ess.neg.,

  3. 3.

in $\mathbf{W}[1]$ if $\Gamma$ is strictly ess.neg. and strictly ess.pos.,

  4. 4.

in $\mathbf{W}[2]$ if $\Gamma$ is strictly ess.neg. or strictly ess.pos.,

  5. 5.

$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-complete if $\Gamma$ is not
Schaefer and $\varepsilon$-valid, and

  6. 6.

$\mathbf{para\text{-}}\mathbf{\Sigma_{2}^{P}}$-complete if $\Gamma$ is not
Schaefer and not $\varepsilon$-valid.

######  Proof 3.2.

(1.) The classical problem $\mathrm{ARG}(\Gamma)$ is already in $\mathbf{P}$
for this case [10, Thm 5.3]. (2.) The upper bound follows because the
unparameterized problem $\mathrm{ARG}(\Gamma)$ is in $\mathbf{NP}$ [10, Prop
5.1]. The lower bound is proven in Lemmas 3.5, 3.7 and 3.9. (3.) is proven in
Lemma 3.11. (4.) is proven in Lemma 3.14.

For (5.) (resp., (6.)), the membership follows because the classical problem
is in $\mathbf{co}\mathbf{NP}$ (resp., $\mathbf{\Sigma_{2}^{P}}$) [10, Thm
5.3]. For hardness of $\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$ when
$\Gamma$ is $\varepsilon$-valid, notice that, since $\Delta$ is
$\varepsilon$-valid, an instance $(\Delta,\alpha)$ of
$\mathrm{p\text{-}}\mathrm{ARG}$ admits an argument if and only if
$\Delta\models\alpha$. The result follows from Lemma 2.21 because the
implication problem is still
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$-hard. Finally, when $\Gamma$ is
not Schaefer and not $\varepsilon$-valid, in the proofs of Creignou et al.
[10, Prop. 5.2] the constructed reductions define $\alpha$ whose length is 2
or 3. Accordingly, either the 2-slice or the 3-slice is
$\mathbf{\Sigma_{2}^{P}}$-hard. This gives the desired hardness result.

For technical reasons we introduce the following variant of the argumentation
existence problem. The problem $\mathrm{ARG}(\Gamma,R)$ asks, given a set of
$\Gamma$-formulas $\Delta$ and an $R$-formula $\alpha$, $\exists$
$\Phi\subseteq\Delta$ s.t. $(\Phi,\alpha)$ is an argument in $\Delta$?

######  Lemma 3.3.

Let $\Gamma,\Gamma^{\prime}$ be two CLs and $R$ a Boolean relation. If
$\Gamma^{\prime}\subseteq\left\langle\Gamma\right\rangle_{\neq}$ and
$R\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$, then
$\mathrm{ARG}(\Gamma^{\prime},R)\leq^{\mathrm{log}}_{m}\mathrm{ARG}(\Gamma)$.

######  Proof 3.4.

Let $(\Delta,\alpha)$ be an instance of the first problem, where
$\Delta=\\{\,\delta_{i}\mid i\in I\,\\}$ and $\alpha=R(x_{1},\dots,x_{k})$. We
map this instance to $(\Delta^{\prime},\alpha^{\prime})$, where
$\Delta^{\prime}=\\{\delta^{\prime}_{i}\mid\delta_{i}\in\Delta\\}$ and
$\alpha^{\prime}$ is a $\Gamma$-formula equivalent to $R(x_{1},\dots,x_{k})$
(which exists because
$R\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$). For $i\in I$ we
obtain $\delta^{\prime}_{i}$ from $\delta_{i}$ by replacing $\delta_{i}$ by an
equivalent $\Gamma$-formula with existential quantifiers (such a
representation exists since
$\Gamma^{\prime}\subseteq\left\langle\Gamma\right\rangle_{\neq}$) and deleting
all existential quantifiers.

Note that the previous result is only used to show lower bounds for specific
slices and, accordingly, is stated in the classical setting.

######  Lemma 3.5.

If the CL $\Gamma$ is neither affine, nor $\varepsilon$-valid, nor ess.pos.,
nor ess.neg., then $\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{NP}$-hard.

######  Proof 3.6.

We give a reduction from the $\mathbf{NP}$-complete problem
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ such that
$|\alpha|$ is constant. An instance of
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ is a
$\mathrm{3CNF}$-formula with only positive literals, the question is to
determine whether there is a satisfying assignment which maps exactly one
variable in each clause to true. We make a case distinction according to the
case (1.) and (3.) in Lemma 2.16. Case (2.) is not needed as if $\Gamma$ is
not affine, not horn and not dual-Horn, then $\Gamma$ can not be
complementive. We first treat case (3.), that is, we have that $(x=y)\land
t\land\neg f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. We then
show that the other two cases can be treated with minor modifications of the
procedure.

Let $\varphi$ be an instance of
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$. We first
reduce $\varphi$ to and instance $(\Delta,\alpha)$ of
$\mathrm{ARG}(\\{\mathrm{T},\mathrm{F},=\\},(x=y)\land t\land\neg f)$, and
then conclude with Lemmas 2.16 and 3.3. Given
$\varphi=\bigwedge_{i=1}^{k}(x_{i}\lor y_{i}\lor z_{i})$, an instance of
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ and let
$t,f,c_{1},\dots,c_{k+1}$ be fresh variables. We let $\Delta$ and $\alpha$ as
following.

$\begin{array}[]{r@{\,}l}\Delta=&\bigcup_{i=1}^{k}\\{x_{i}\land\neg{y_{i}}\land\neg{z_{i}}\land(c_{i}=c_{i+1})\land
t\land\neg f\\}\\\ \cup&\bigcup_{i=1}^{k}\\{\neg{x_{i}}\land
y_{i}\land\neg{z_{i}}\land(c_{i}=c_{i+1})\land t\land\neg f\\}\\\
\cup&\bigcup_{i=1}^{k}\\{\neg{x_{i}}\land\neg{y_{i}}\land
z_{i}\land(c_{i}=c_{i+1})\land t\land\neg f\\},\\\
\alpha=&(c_{1}=c_{k+1})\land t\land\neg f.\end{array}$

Note that any formula in $\Delta$ is expressible as $\Gamma$-formula since
$\\{\mathrm{T},\mathrm{F},=\\}\subseteq\mathsf{IM}_{2}\subseteq\left\langle\Gamma\right\rangle$
(cf. [26, Table 1]). Since by Lemma 2.14,
$\left\langle\Gamma\right\rangle_{\neq}=\left\langle\Gamma\right\rangle$ and
by construction $(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$, we have, by Lemma
3.3, the desired reduction to
$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$. Note that in the reduction
of Lemma 3.3 the size of $\alpha$ is always constant.

For case (1.) of Lemma 2.16 we have that $(x\neq y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. To cope with this
change in the reduction we introduce one additional variable $d$ and replace
$\alpha$ by $(c_{1}\neq d)\land(d\neq c_{k+1})\land t\land\neg f$.

######  Lemma 3.7.

If the CL $\Gamma$ is affine, neither $\varepsilon$-valid, nor ess. pos., nor
ess.neg., then $\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{NP}$-hard.

######  Proof 3.8.

We proceed analogously to the proof of Lemma 3.5. We give a reduction from the
$\mathbf{NP}$-complete problem
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ such that
$|\alpha|$ is constant. We make a case distinction according to case (1.) and
(2.) in Lemma 2.16 (case 3. can not occur for $\Gamma$ is affine and not
ess.pos.). First, we treat the second case, that is, we have that $(x\neq
y)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. Then, we show that
the first case can be treated with minor modifications of the procedure.

Now, we reduce
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ to
$\mathrm{ARG}(\\{=,\neq\\},\\{\neq\\})$, and then conclude with Lemmas 2.16
and 3.3. We give the following reduction. Let
$\varphi=\bigwedge_{i=1}^{k}(x_{i}\lor y_{i}\lor z_{i})$ be an instance of
$\mathrm{Pos}\text{-1-}\mathrm{In}\text{-}3\text{-}\mathrm{Sat}$ and let
$t,d,c_{1},\dots,c_{k+1}$ be fresh variables. We map $\varphi$ to
$(\Delta,\alpha)$, where

$\begin{array}[]{@{}r@{\,}l@{}}\Delta=&\bigcup_{i=1}^{k}\\{(x_{i}=t)\land(y_{i}\neq
t)\land(z_{i}\neq t)\land(c_{i}=c_{i+1})\\}\\\
\cup&\bigcup_{i=1}^{k}\\{(x_{i}\neq t)\land(y_{i}=t)\land(z_{i}\neq
t)\land(c_{i}=c_{i+1})\\}\\\ \cup&\bigcup_{i=1}^{k}\\{(x_{i}\neq
t)\land(y_{i}\neq t)\land(z_{i}=t)\land(c_{i}=c_{i+1})\\},\\\
\alpha=&(c_{1}\neq d)\land(d\neq c_{k+1}).\end{array}$

Note that any formula in $\Delta$ is expressible as $\Gamma$-formula since
$\\{=,\neq\\}\subseteq\mathsf{ID}\subseteq\left\langle\Gamma\right\rangle$
(cf. [26, Table 1]). Since by Lemma 2.14
$\left\langle\Gamma\right\rangle_{\neq}=\left\langle\Gamma\right\rangle$ and
by construction $(x\neq
y)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$, we have by Lemma 3.3
the desired reduction to $\mathrm{p\text{-}}\mathrm{ARG}(\Gamma)$. Note that
in the reduction of Lemma 3.3 the size of $\alpha$ is always constant.

For case (1.) of Lemma 2.16 we have that $(x\neq y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. To cope with this
change in the reduction, we introduce one additional variable $f$ and add the
constraints $t\land\neg f$ to $\alpha$ as well as to every formula in $\Delta$
.

######  Lemma 3.9.

Let $\Gamma$ be a CL that is not $\varepsilon$-valid. If $\Gamma$ is ess.pos.
and not strictly ess.pos. or ess.neg. and not strictly ess.neg., then
$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)$ is
$\mathbf{para\text{-}}\mathbf{NP}$-hard.

######  Proof 3.10.

We can use exactly the same reduction as in Lemma 3.5, except we do not
require a case distinction. Note that, by Proposition 2.18, we have that
$(t\land\neg f)\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. Since
$\exists f\,(t\land\neg f)\equiv\mathrm{T}(t)$ and $\exists t\,(t\land\neg
f)\equiv\mathrm{F}(f)$, we conclude that
$\mathrm{T},\mathrm{F}\in\left\langle\Gamma\right\rangle_{\neq}$. Further, by
Lemma 2.14, we have that $(x=y)\in\left\langle\Gamma\right\rangle_{\neq}$.
Together we have
$\\{\mathrm{T},\mathrm{F},=\\}\subseteq\left\langle\Gamma\right\rangle_{\neq}$,
and thus any formula in $\Delta$ is expressible as $\Gamma$-formula with
existential quantifiers but without equality. By Lemma 2.12, it follows that
$(x=y)\land t\land\neg
f\in\left\langle\Gamma\right\rangle_{\not\exists,\neq}$. Hence we can apply
Lemma 3.3 to conclude.

######  Lemma 3.11.

Let $\Gamma$ be a CL that is strictly ess.neg. and strictly ess.pos., then
$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)\in\mathbf{W}[1]$.

######  Proof 3.12.

We give a reduction to the $\mathbf{W}[1]$-complete problem Clique. Note that
by definition of strictly ess.pos. and strictly ess.neg., any $\Gamma$-formula
can be written as a $\\{\mathrm{T},\mathrm{F}\\}$-formula. Let
$(\Delta,\alpha)$ be an instance of
$\mathrm{ARG}(\\{\mathrm{T},\mathrm{F}\\},|\alpha|)$. Note that $\Delta$ is a
set of terms and $\alpha$ is also a term. Let $\Delta=\\{t_{1},\dots,t_{n}\\}$
and $\alpha=l_{1}\land\dots\land l_{k}$. Then we have the following two
observations.

Observation 1:

There is a support for $\alpha$ iff there is a support of cardinality at most
$k$: If $l_{i}$ can be explained at all, then one $\varphi\in\Delta$ is
sufficient. In other words, there is no $l_{i}$ in $\alpha$ such that a
combination of two terms from $\Delta$ is necessary to explain $l_{i}$.

Observation 2:

If a set of terms is pairwise consistent, then the whole set is consistent. If
a set of terms is inconsistent, then there are two terms which are pairwise
inconsistent.

For each literal $l_{i}\in\alpha$, form the sets
$L^{+}_{i}=\\{\,t\in\Delta\mid l_{i}\in t\,\\}$ and
$L^{-}_{i}=\\{\,t\in\Delta\mid\neg l_{i}\in t\,\\}$. That is, each $t\in
L^{+}_{i}$ is a candidate support, whereas, no $t\in L^{-}_{i}$ can be in the
support, for every $i\leq k$. Let $N=\bigcup\limits_{i\leq k}L^{-}_{i}$ and
denote $L_{i}=L^{+}_{i}\backslash N$. It is important to notice that there is
a support only if $L_{i}\not=\emptyset$ for each $i\leq k$. Otherwise, for
some $i$, the support $\Phi$ can not contain a term $t$ supporting $l_{i}$
such that $\Phi$ is consistent. It remains to determine whether $\Phi$, that
includes one $t$ from each $L_{i}$ is consistent. The consistency still needs
to be checked because terms in $\Delta$ may contain literals not in $\alpha$.
That is, care should be taken when selecting which terms to include in the
support.

Consider the following graph $\mathcal{G}=(V,E)$. There is one node
corresponding to each element $t_{j}$ and each set $L_{i}$. By slightly
abusing the notation, we write $V=\bigcup\limits_{i\leq k}L_{i}$. It is worth
mentioning that if a term appears in two different sets, say $L_{r}$ and
$L_{s}$, then there are distinct nodes for each term. We will explain later
why this is required. Finally, the edge relation denotes the pairwise
consistency of terms. That is, there is an edge between a term $t_{r,i}\in
L_{i}$ and $t_{s,j}\in L_{j}$ if $t_{r,i}\land t_{s,j}$ is consistent.
However, there is no edge between $t_{r,i}$ and $t_{s,i}$. That is, if the two
terms belong to the same set $L_{i}$, or if two terms belong to two different
sets $L_{i}$ and $L_{j}$ but these are pairwise inconsistent, then there is no
edge.

We first prove that the reduction is indeed $\mathbf{FPT}$. The sets
$L^{+}_{i}$ and $L^{-}_{i}$ can be computed in polynomial time. The size of
$V$ is $O(k\cdot n^{2})$, because there are $k$ sets of the form $L_{i}$, each
contains at most $n$ terms of size at most $n$ (where $n$ is the input size).
To draw the edges, for each element $t\in L_{1}$, one needs to check the
pairwise consistency for each of the remaining $k-1$ sets, each of size
$O(n^{2})$. This gives $O(k\cdot n^{3})$ time for one element of $L_{1}$. To
determine edges for each element of $L_{1}$, it requires $n\cdot O(k\cdot
n^{3})=O(k\cdot n^{4})$ time. Finally, to repeat this for each set $L_{i}$, it
requires $O(k^{2}\cdot n^{4})$ time. This proves that the reduction can be
preformed in $\mathbf{FPT}$-time.

Now we prove that the reduction preserves the cliques of $\mathcal{G}$ of size
$k$ and the supports of $(\Delta,\alpha)$.

######  Claim 1.

$(V,E)$ admits a clique of size $k$ if and only if $(\Delta,\alpha)$ admits a
support.

######  Proof 3.13 (Proof of Claim 1).

“$\Rightarrow$”. Let $S\subseteq V$ be a clique of size $k$ in $(V,E)$. Since
there are no edges between the two elements from the same set $L_{i}$, this
implies $S$ contains exactly one term from each $L_{i}$. Furthermore, the fact
that $S$ is a clique implies that the set of terms is consistent. This
provides a support for $\alpha$.

“$\Leftarrow$”. Let $\Phi$ be a support for $\alpha$ in $\Delta$. According to
observation 1, for each $l_{i}\in\alpha$, there is a term $t\in\Delta$ such
that $t\models l_{i}$. The set $L_{i}$ contains every such a $t\in\Delta$.
Moreover, this holds for each $l_{i}\in\alpha$, this implies that $\Phi$
contains at least one $t$ from $L_{i}$ for each $i\leq k$. Finally, since
$\Phi$ is consistent, this implies that every pair of nodes corresponding to
the terms in $\Phi$ contains an edge. This gives a clique in $(V,E)$.

It might happen that there is one term $t\in\Delta$ such that $t\models
l_{i}\land l_{j}$, and due to our construction, $t\in L_{i}\cap L_{j}$.
However, the graph contains two separate nodes for each occurrence of $t$.
This is required to ensure that a support of size smaller than $k$ also
guarantees a clique of size $k$ for $(V,E)$.

######  Lemma 3.14.

Let $\Gamma$ be a CL that is strictly ess.neg. or strictly ess.pos., then
$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\alpha|)\in\mathbf{W}[2]$.

######  Proof 3.15.

We only prove the statement for $\Gamma$ that is strict ess.pos. The other
case is proven analogously. Since we consider only finite constraint languages
we have that $\Gamma\subseteq\mathsf{IS}^{r}_{02}$ for some $r\geq 2$.
Therefore, any $\Gamma$-formula can be written as a conjunction of positive or
negative literals and positive clauses of size at most $r$.

Let $\Delta=\\{e_{1},\dots,e_{n}\\}$ and $\alpha=a_{1}\land\dots\land a_{k}$,
where each $a_{i}$ is either a positive or negative literal, or a positive
clause of size $\leq r$. Then we have the following three claims.

######  Claim 2.

If $a_{i}$ can be explained at all, then at most $r$ formulas from $\Delta$
are sufficient. Consequently, there is a support for $\alpha$ iff there is a
support of size at most $r\cdot k$.

######  Proof 3.16 (Proof of Claim 2).

If $a_{i}$ is a negative literal, then at most $1$ formula from $\Delta$ is
sufficient (one that contains $a_{i}$). If $a_{i}$ is a positive literal, then
at most $r$ formulas from $\Delta$ are sufficient (worst case: one
$e\in\Delta$ contains a (positive) clause which contains $a_{i}$, then we need
at most $r-1$ more $e$’s in order to force all other variables in the clause
to $0$). If $a_{i}$ is a positive clause, then it suffices to explain one
variable from that clause, as a result, as in the previous case, at most $r$
formulas from $\Delta$ are sufficient. In other words, there is no $a_{i}$ in
$\alpha$ such that more than $r$ formulas from $\Delta$ are necessary to
explain $a_{i}$.

######  Claim 3.

Let $\Phi\subseteq\Delta$. If all subsets of $\Phi$ of size $r+1$ are
consistent, then $\Phi$ is consistent. In contra position: If $\Phi$ is
inconsistent, then it contains a subset of size at most $r+1$ which is
inconsistent.

######  Proof 3.17 (Proof of Claim 3).

Similar to the previous proof: the worst case to create an inconsistency is to
take a formula containing a positive clause of size $r$ and then $r$ formulas
forcing together all variables from the positive clause to 0.
Let $U=\\{u_{1},\dots,u_{m}\\}$ be a collection of fresh variables, where each
variable will represent a different subset of $\Delta$ of size at most $r$,
that is, $m\leq r\cdot|\Delta|^{r}$. For each $u_{i}$ denote by $S(u_{i})$ the
subset of $\Delta$ it represents. For $V\subseteq U$ define
$S(V)=\bigcup_{u_{i}\in V}S(u_{i})$. Define

$L_{i}=\bigvee_{S(u_{j})\models a_{i}}u_{j}$

and

$\varphi=\bigwedge_{i=1}^{k}L_{i}\land\bigwedge_{V\subseteq Us.t.|V|\leq
r+1\text{ and }S(V)\models\emptyset}\Big{(}\bigvee_{u_{i}\in V}(\neg
u_{i})\Big{)}$

The role of each $L_{i}$ is to make sure that each $a_{i}$ is explained. The
role of the negative clauses in $\varphi$ is to make sure that inconsistent
explanations are forbidden.

######  Claim 4.

$(\Delta,\alpha)$ admits a support iff $\varphi$ is satisfiable iff $\varphi$
has a model of weight at most $k$.

######  Proof 3.18 (Proof of Claim 4).

Be $\Phi\subseteq\Delta$ a support for $\alpha$. Since $\Phi$ explains each
$a_{i}$, by observation 1 there is a set $E(a_{i})\subseteq\Phi$ of size at
most $r$ such that $E(a_{i})\models a_{i}$. By construction each $E(a_{i})$
corresponds to a $u_{j}\in U$. One verifies that these $u_{j}$’s constitute a
model of $\varphi$ of weight at most $k$ (if $i\neq j$ it can happen that
$E(a_{i})=E(a_{j})$, therefore _at most_).

For the other direction let $\varphi$ be satisfiable. By construction of
$\varphi$ there is a model of weight at most $k$ (in each $L_{i}$ it is
sufficient to have at most one positive literal). Be $W\subseteq U$ such a
model of weight at most $k$. By construction of $\varphi$ the set $S(W)$ is
consistent and explains each $a_{i}$. Therefore, $S(W)$ constitutes a support
for $\alpha$.

Our final map is $(\Delta,\alpha)\mapsto\varphi\land\bigvee_{i=1}^{k+1}x_{i}$,
where $x_{i}$ are fresh variables. We conclude by observing that $\varphi$ is
satisfiable if and only if $\varphi\land\bigvee_{i=1}^{k+1}x_{i}$ is
$(k+1)$-satisfiable.

######  Theorem 3.19.

$\mathrm{p\text{-}}\mathrm{ARG\text{-}Check}(\Gamma,|\alpha|)$, for a CL
$\Gamma$, is (1.) $\mathbf{FPT}$ if $\Gamma$ is Schaefer, and (2.)
$\mathbf{para\text{-}}\mathbf{DP}$-complete otherwise.

######  Proof 3.20.

  1. 1.

This follows from [10, Theorem 6.1] as classically
$\mathrm{ARG\text{-}Rel}(\Gamma)\in\mathbf{P}$.

  2. 2.

Here, the membership follows as classically
$\mathrm{ARG\text{-}Rel}(\Gamma)\in\mathbf{DP}$. Furthermore, the reduction in
the proof of [10, Propositions 6.3 and 6.4] always uses a fixed size of the
claim $\alpha$. As a consequence, certain slices of
$\mathrm{ARG\text{-}Check}(\Gamma)$ are $\mathbf{DP}$-hard, giving the desired
results.

######  Theorem 3.21.

$\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}(\Gamma,|\alpha|)$, for a CL
$\Gamma$, is

  1. 1.

$\mathbf{FPT}$ if $\Gamma$ is either positive or negative.

  2. 2.

$\mathbf{para\text{-}}\mathbf{NP}$-complete if $\Gamma$ is Schaefer but
neither strictly ess.neg. nor strictly ess.pos.

  3. 3.

$\mathbf{para\text{-}}\mathbf{\Sigma_{2}^{P}}$-complete if $\Gamma$ is not
Schaefer.

######  Proof 3.22.

  1. 1.

This follows as classically $\mathrm{ARG\text{-}Rel}(\Gamma)\in\mathbf{P}$ by
[10, Prop. 7.3].

  2. 2.

Here, the membership follows because the classical problem is in
$\mathbf{NP}$. We make a case distinction as whether $\Gamma$ is
$\varepsilon$-valid or not.

Case 1.

Let $\Gamma$ be Schaefer and $\varepsilon$-valid, but neither positive nor
negative. The hardness follows because the $2$-slice of the problem is already
$\mathbf{NP}$-hard [10, Proposition 7.6].

Case 2.

Let $\Gamma$ be Schaefer but neither $\varepsilon$-valid, nor strictly
ess.neg. or strictly ess.pos The hardness follows from Theorem 3.1. This is
due to the reason that $\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}$ is always
harder than $\mathrm{p\text{-}}\mathrm{ARG}$ via the reduction
$(\Delta,\alpha)\mapsto(\Delta\cup\\{\psi\\},\psi,\alpha)$.

  3. 3.

In this case, the membership is true because the classical problem is in
$\mathbf{\Sigma_{2}^{P}}$. Hardness follows from a result of [10, Prop. 7.7].
Notice that, while proving the hardness for each sub case, the claim $\alpha$
has fixed size in each reduction. This implies that certain slices in each
case are $\mathbf{\Sigma_{2}^{P}}$-hard, consequently, giving the desired
hardness results.

##  4 Parameters: Size of Support, Knowledge-Base

Regarding these parameters, we will always show a dichotomy: for the Schaefer
cases, the problem is $\mathbf{FPT}$, otherwise we have a lower bound by the
implication problem.

Recall that the collection $\Delta$ of formulas is not assumed to be
consistent.

######  Theorem 4.1.

$\mathrm{p\text{-}}\mathrm{ARG}(\Gamma,|\Delta|)$ and
$\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}(\Gamma,|\Delta|)$, for CLs
$\Gamma$, are (1.) $\mathbf{FPT}$ if $\Gamma$ is Schaefer, and (2.)
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\Phi|)$-hard and in
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$ otherwise.

######  Proof 4.2.

  1. 1.

Notice that the number of subsets of $\Delta$ is bounded by the parameter.
Consequently, one simply checks each subset of $\Delta$ as a possible support
$\Phi$ for $\alpha$. Moreover, the size of each support $\Phi$ is also bounded
by the parameter, as a result, one can determine the satisfiability and
entailment in $\mathbf{FPT}$-time. This is because, the satisfiability and
entailment for Schaefer languages is in $\mathbf{P}$.

  2. 2.

For the lower bound, we have
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\Phi|)\leq^{\mathrm{\mathbf{FPT}}}\mathrm{ARG}(\Gamma,|\Delta|)\leq^{\mathrm{\mathbf{FPT}}}\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}(\Gamma,|\Delta|)$
by identities.

For membership, we make case distinction as whether $\Gamma$ is
$\varepsilon$-valid or not.

Case 1.

$\Gamma$ is $\varepsilon$-valid. The membership follows because the
unparameterized problem $\mathrm{ARG}(\Gamma)$ is in $\mathbf{co}\mathbf{NP}$
when $\Gamma$ is $\varepsilon$-valid.

Case 2.

$\Gamma$ is neither $0$-valid nor $1$-valid. The membership follows because
for each candidate $\Phi$, one needs to determine whether $\Phi$ is consistent
and $\Phi\models\alpha$. The consistency can be checked in $\mathbf{FPT}$-time
because $|\Phi|$ is bounded by the parameter. The entailment problem for non-
Schaefer, non $\varepsilon$-valid languages is still in
$\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$ when $|\Phi|$ is the parameter.

For
$\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}(\Gamma,|\Delta|)\in\mathbf{para\text{-}}\mathbf{co}\mathbf{NP}$,
try all the subsets of $\Delta$ that contain $\psi$, as a candidate support.

When the support size $|\Phi|$ is considered as a parameter, the problems
$\mathrm{ARG}$ and $\mathrm{ARG\text{-}Rel}$ become irrelevant. Consequently,
we only consider the problem $\mathrm{ARG\text{-}Check}$.

######  Corollary 4.3.

$\mathrm{p\text{-}}\mathrm{ARG\text{-}Check}(\Gamma,|\Phi|)$, for a CL
$\Gamma$, is (1.) $\mathbf{FPT}$ if $\Gamma$ is Schaefer, and (2.)
$\mathrm{p\text{-}}\mathrm{IMP}(\Gamma,|\Phi|)$-hard and in
$\mathbf{para\text{-}}\mathbf{DP}$ otherwise.

##  5 Conclusion and Outlook

In this paper, we performed a two dimensional classification of reasoning in
logic-based argumentation. On the one side, we studied syntactical fragments
in the spirit of Schaefer’s framework of co-clones. On the other side, we
analysed a list of parameters and classified the parameterized complexity of
three central reasoning problems accordingly.

As a take-away message we get that $\alpha$ as a parameter does not help to
reach tractable fragments of $\mathrm{p\text{-}}\mathrm{ARG}$.

The case for $\mathrm{p\text{-}}\mathrm{ARG\text{-}Rel}(\Gamma,|\alpha|)$ when
$\Gamma$ is strictly ess.neg. or strictly ess.pos. is still open. Also, few
tight complexity results have to be found and the implication problem
regarding the parameter $|\Phi|$ has to be understood.

It is worth noting that for some CLs, e.g., those that are
$\varepsilon$-valid, the problem $\mathrm{p\text{-}}\mathrm{ARG\text{-}Check}$
is harder than $\mathrm{p\text{-}}\mathrm{ARG}$. This is because the problem
$\mathrm{p\text{-}}\mathrm{ARG}$ under consideration is the decision problem.
Having the identity reduction from
$\mathrm{p\text{-}}\mathrm{ARG\text{-}Check}$ to
$\mathrm{p\text{-}}\mathrm{ARG}$ shows that the minimality is checked by
solving the problem $\mathrm{p\text{-}}\mathrm{ARG}$, already. This shows that
computing a minimal support is potentially harder than deciding whether such a
support exists, unless the complexity classes $\mathbf{DP}$ and
$\mathbf{co}\mathbf{NP}$ coincide. We pose as an interesting open problem to
classify the function version of $\mathrm{ARG}$, in both, the classical and
the parameterized setting.

Regarding other parameters, treewidth [33] is a quite promising structural
property that led to several $\mathbf{FPT}$-results in the parameterized
setting: artificial intelligence [22], knowledge representation [20],
abduction in Datalog [21], and databases [23]. Fellows et al. [17] show that
abductive reasoning benefits from this parameter as well. Using a reduction
between abduction and argumentation [10] might yield $\mathbf{FPT}$-results in
our setting. Furthermore, we plan to give a precise classification of
$\mathrm{p\text{-}}\mathrm{IMP}$.

As further future work, we plan investigating the (parameterized) enumeration
complexity [19, 13, 12, 27] of reasoning in this setting.

## References

  * [1] Leila Amgoud and Henri Prade.  Using arguments for making and explaining decisions.  Artif. Intell., 173(3-4):413–436, 2009.
  * [2] Katie Atkinson, Pietro Baroni, Massimiliano Giacomin, Anthony Hunter, Henry Prakken, Chris Reed, Guillermo Ricardo Simari, Matthias Thimm, and Serena Villata.  Towards artificial argumentation.  AI Mag., 38(3):25–36, 2017.  doi:10.1609/aimag.v38i3.2704.
  * [3] Pietro Baroni, Dov Gabbay, Massimiliano Giacomin, and Leendert van der Torre, editors.  Handbook of Formal Argumentation.  College Publications, 2018.
  * [4] Philippe Besnard and Anthony Hunter.  A logic-based theory of deductive arguments.  Artif. Intell., 128(1-2):203–235, 2001.
  * [5] Philippe Besnard and Anthony Hunter.  Elements of Argumentation.  MIT Press, 2008.
  * [6] Olaf Beyersdorff, Arne Meier, Michael Thomas, and Heribert Vollmer.  The complexity of propositional implication.  Inf. Process. Lett., 109(18):1071–1077, 2009.  doi:10.1016/j.ipl.2009.06.015.
  * [7] Elmar Böhler, Steffen Reith, Henning Schnoor, and Heribert Vollmer.  Bases for boolean co-clones.  Inf. Process. Lett., 96(2):59–66, 2005.  doi:10.1016/j.ipl.2005.06.003.
  * [8] Elmar Böhler, Nadia Creignou, Steffen Reith, and Heribert Vollmer.  Playing with boolean blocks, part ii: Constraint satisfaction problems.  ACM SIGACT-Newsletter, 35, 2004.
  * [9] Carlos Iván Chesñevar, Ana Gabriela Maguitman, and Ronald Prescott Loui.  Logical models of argument.  ACM Comput. Surv., 32(4):337–383, 2000.
  * [10] Nadia Creignou, Uwe Egly, and Johannes Schmidt.  Complexity classifications for logic-based argumentation.  ACM Trans. Comput. Log., 15(3):19:1–19:20, 2014.  doi:10.1145/2629421.
  * [11] Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.  Complexity classifications of Boolean constraint satisfaction problems, volume 7 of SIAM monographs on discrete mathematics and applications.  SIAM, 2001.
  * [12] Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive, and Heribert Vollmer.  Parameterised enumeration for modification problems.  Algorithms, 12(9):189, 2019.  doi:10.3390/a12090189.
  * [13] Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer.  Paradigms for parameterized enumeration.  Theory Comput. Syst., 60(4):737–758, 2017.  doi:10.1007/s00224-016-9702-4.
  * [14] Nadia Creignou, Johannes Schmidt, Michael Thomas, and Stefan Woltran.  Complexity of logic-based argumentation in post’s framework.  Argument & Computation, 2(2-3):107–129, 2011.
  * [15] Rodney G. Downey and Michael R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [16] Phan Minh Dung.  On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games.  Artif. Intell., 77(2):321–358, 1995.
  * [17] Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond, and Stefan Rümmele.  The parameterized complexity of abduction.  In Jörg Hoffmann and Bart Selman, editors, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada. AAAI Press, 2012.  URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/5048.
  * [18] Johannes Klaus Fichte, Markus Hecher, and Arne Meier.  Counting complexity for reasoning in abstract argumentation.  In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 2827–2834. AAAI Press, 2019\.  doi:10.1609/aaai.v33i01.33012827.
  * [19] Fedor V. Fomin and Dieter Kratsch.  Exact Exponential Algorithms.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010\.  doi:10.1007/978-3-642-16533-7.
  * [20] Georg Gottlob, Reinhard Pichler, and Fang Wei.  Bounded treewidth as a key to tractability of knowledge representation and reasoning.  In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, pages 250–256. AAAI Press, 2006.
  * [21] Georg Gottlob, Reinhard Pichler, and Fang Wei.  Efficient datalog abduction through bounded treewidth.  In AAAI, pages 1626–1631, 2007.
  * [22] Georg Gottlob and Stefan Szeider.  Fixed-Parameter Algorithms For Artificial Intelligence, Constraint Satisfaction and Database Problems.  The Computer Journal, 51(3):303–325, 09 2007.  doi:10.1093/comjnl/bxm056.
  * [23] Martin Grohe.  The complexity of homomorphism and constraint satisfaction problems seen from the other side.  J. ACM, 54(1), March 2007.  doi:10.1145/1206035.1206036.
  * [24] Paolo Liberatore.  Redundancy in logic I: CNF propositional formulae.  Artif. Intell., 163(2):203–232, 2005.
  * [25] Yasir Mahmood, Arne Meier, and Johannes Schmidt.  Parameterised complexity for abduction.  CoRR, abs/1906.00703, 2019.  URL: http://arxiv.org/abs/1906.00703, arXiv:1906.00703.
  * [26] Yasir Mahmood, Arne Meier, and Johannes Schmidt.  Parameterised complexity of abduction in schaefer’s framework.  In Logical Foundations of Computer Science - International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4-7, 2020, Proceedings, pages 195–213, 2020.  doi:10.1007/978-3-030-36755-8\\_13.
  * [27] Arne Meier.  Parametrised enumeration.  Habilitation thesis, Leibniz Universität Hannover, 2020.  doi:10.15488/9427.
  * [28] Gustav Nordh and Bruno Zanuttini.  What makes propositional abduction tractable.  Artif. Intell., 172(10):1245–1284, 2008.  doi:10.1016/j.artint.2008.02.001.
  * [29] Simon Parsons, Michael J. Wooldridge, and Leila Amgoud.  Properties and complexity of some formal inter-agent dialogues.  J. Log. Comput., 13(3):347–376, 2003.
  * [30] Emil L. Post.  The two-valued iterative systems of mathematical logic.  Annals of Mathematical Studies, 5:1–122, 1941.
  * [31] Henry Prakken and Gerard Vreeswijk.  Logics for Defeasible Argumentation, pages 219–318.  Springer Netherlands, Dordrecht, 2002.
  * [32] Antonio Rago, Oana Cocarascu, and Francesca Toni.  Argumentation-based recommendations: Fantastic explanations and how to find them.  In IJCAI, pages 1949–1955. ijcai.org, 2018.
  * [33] Neil Robertson and Paul D. Seymour.  Graph minors. III. planar tree-width.  J. Comb. Theory, Ser. B, 36(1):49–64, 1984.  doi:10.1016/0095-8956(84)90013-3.
  * [34] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Richard J. Lipton, Walter A. Burkhard, Walter J. Savitch, Emily P. Friedman, and Alfred V. Aho, editors, Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216–226. ACM, 1978.  doi:10.1145/800133.804350.
  * [35] Henning Schnoor and Ilka Schnoor.  Partial polymorphisms and constraint satisfaction problems.  In Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], pages 229–254, 2008.  doi:10.1007/978-3-540-92800-3\\_9.
  * [36] Michael Sipser.  Introduction to the theory of computation.  PWS Publishing Company, 1997.