# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
_Parameter:_ The maximum number of times that any atom occurs in \(P\). _Question:_ Does \(P\) have an answer set? ```

```
``` ASP-consistency(\(\#\)cont.rules)

_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of contingent rules of \(P\). _Question:_ Does \(P\) have an answer set? ```  
```
ASP-consistency(\(\#\)disj.rules)

_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of disjunctive rules of \(P\). _Question:_ Does \(P\) have an answer set? ```  
```
ASP-consistency(\(\#\)dual-normal.rules)

_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The number of rules of \(P\) that are dual-normal. _Question:_ Does \(P\) have an answer set? ```  
```
ASP-consistency(str.norm.bd-size)

_Instance:_ A disjunctive logic program \(P\). _Parameter:_ The size of the smallest normality-backdoor for \(P\). _Question:_ Does \(P\) have an answer set? ```  
```
ASP-consistency(max.atom.occ.) _Instance:_ A disjunctive logic program \(P\). _Parameter:_ The maximum number of times that any atom occurs in \(P\). _Question:_ Does \(P\) have an answer set? ```  
```
```
``` ASP-consistency(str.norm.bd-size)

_Instance:_ A



that does not violate any constraint in \(C\), it holds that \(\alpha\) can be extended to a solution for the CSP instance \((X,D,C)\). Robust-CSP-Sat

_Instance:_ A CSP instance \((X,D,C)\), and an integer \(k\). _Parameter:_\(k\). _Question:_ Is \((X,D,C)\)\(k\)-robustly satisfiable? **Complexity:**\(\Pi^{\mathrm{P}}_{2}[k*]\)-complete [7; 30]. ### Abductive Reasoning

The setting of (propositional) abductive reasoning can be formalized as follows. An _abduction instance_\(\mathcal{P}\) consists of a tuple \((V,H,M,T)\), where \(V\) is the set of _variables_, \(H\subseteq V\) is the set of _hypotheses_, \(M\subseteq V\) is the set of _manifestations_, and \(T\) is the theory, a formula in CNF over \(V\). It is required that \(M\cap H=\emptyset\). A set \(S\subseteq H\) is a _solution_ (or _explanation_) of \(\mathcal{P}\) if (i) \(T\cup S\) is consistent and (ii) \(T\cup S\models M\). One central problem is to decide, given an abduction instance \(\mathcal{P}\) and an integer \(m\), whether there exists a solution \(S\) of \(\mathcal{P}\) of size at most \(m\). This problem is \(\Sigma^{\mathrm{P}}_{2}\)-complete in general [53]. Abduction(Krom-bd-size):

_Input:_ an abduction instance \(\mathcal{P}=(V,H,M,T)\), and a positive integer \(m\). _Parameter:_ The size of the smallest strong 2 CNF-backdoor for \(T\). _Question:_ Does there exist a solution \(S\) of \(\mathcal{P}\) of size at most \(m\)? **Complexity:**\(\Sigma^{\mathrm{P}}_{2}[*k,1]\)-complete [7]. Abduction(Horn-bd-size):

_Input:_ an abduction instance \(\mathcal{P}=(V,H,M,T)\), and a positive integer \(m\). _Parameter:_ The size of the smallest strong Horn-backdoor for \(T\). _Question:_ Does there exist a solution \(S\) of \(\mathcal{P}\) of size at most \(m\)? **Complexity:** para-NP-complete [31]. Abduction(#non-Horn-clauses):

_Input:_ an abduction instance \(\mathcal{P}=(V,H,M,T)\), and a positive integer \(m\). _Parameter:_ The size of the smallest strong Horn-backdoor for \(T\). _Question:_ Does there exist a solution \(S\) of \(\mathcal{P}\) of size at most \(m\)? **Complexity:** para-NP-complete [31]. Abduction(#non-Horn-clauses):

_Input:_ an abduction instance \(\mathcal{P}=(V,H,M,T)\), and a positive integer \(m\). _Parameter:_ The number of clauses in \(T\) that are not Horn. _Question:_ Does there exist a solution \(S\) of \(\mathcal{P}\) of size at most \(m\)? **Complexity:**\(\Sigma^{\mathrm{P}}_{2}[*k,\mathrm{P}]\)-complete [7]. ## 5 Graph Problems

### Clique Extensions

Let \(G=(V,E)\) be a graph. A clique \(C\subseteq V\) of \(G\) is a subset of vertices that induces a complete subgraph of \(G\), i.e., \(\{v,v^{\prime}\}\in E\) for all \(v,v^{\prime}\in C\) such that \(v\
eq v^{\prime}\). The \(W[1]\)-complete problem of determining whether a graph has a clique of size \(k\) is an important problem in the W-hierarchy, and is used in many \(\mathrm{W}[1]\)-hardness proofs.