# A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
## 4 Knowledge Representation and Reasoning Problems
### Disjunctive Answer Set Programming
We consider a related problem that is complete for \(\Pi^{\mathrm{P}}_{2}[*k,1]\). Small-Clique-Extension

_Instance:_ A graph \(G=(V,E)\), a subset \(V^{\prime}\subseteq V\), and an integer \(k\). _Parameter:_\(k\). _Question:_ Is it the case that for each clique \(C\subseteq V^{\prime}\), there is some \(k\)-clique \(D\) of \(G\) such that \(C\cup D\) is a \((|C|+k)\)-clique? **Complexity:**\(\Pi^{\mathrm{P}}_{2}[*k,1]\)-complete [7]. ### Graph Coloring Extensions

The following problem related to extending colorings to the leaves of a graph to a coloring on the entire graph, is \(\Pi^{\mathrm{P}}_{2}\)-complete in the most general setting [54]. Let \(G=(V,E)\) be a graph. We will denote those vertices \(v\) that have degree \(1\) by _leaves_. We call a (partial) function \(c:V\to\{1,2,3\}\) a _\(3\)-coloring (of \(G\))_. Moreover, we say that a \(3\)-coloring \(c\) is _proper_ if \(c\) assigns a color to every vertex \(v\in V\), and if for each edge \(e=\{v_{1},v_{2}\}\in E\) it holds that \(c(v_{1})\
eq c(v_{2})\). The problem of deciding, given a graph \(G=(V,E)\) with \(n\) many leaves and an integer \(m\), whether any \(3\)-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) can be extended to a proper \(3\)-coloring of \(G\), is \(\Pi^{\mathrm{P}}_{2}\)-complete [54]. We consider several parameterizations. 3-Coloring-Extension(degree)

_Instance:_ a graph \(G=(V,E)\) with \(n\) many leaves, and an integer \(m\). _Parameter:_ the degree of \(G\). _Question:_ can any \(3\)-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) be extended to a proper \(3\)-coloring of \(G\)? **Complexity:** para-\(\Pi^{\mathrm{P}}_{2}\)-complete [7; 41]. 3-Coloring-Extension(#leaves)

_Instance:_ a graph \(G=(V,E)\) with \(n\) many leaves, and an integer \(m\). _Parameter:_\(n\). _Question:_ can any \(3\)-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) be extended to a proper \(3\)-coloring of \(G\)? **Complexity:** para-NP-complete [7; 41]. 3-Coloring-Extension(#col.leaves)

_Instance:_ a graph \(G=(V,E)\) with \(n\) many leaves, and an integer \(m\). _Parameter:_\(m\). _Question:_ can any \(3\)-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) be extended to a proper \(3\)-coloring of \(G\)? **Complexity:** para-NP-complete [7; 41]. 3-Coloring-Extension(#col.leaves)

_Instance:_ a graph \(G=(V,E)\) with \(n\) many leaves, and an integer \(m\). _Parameter:_\(m\). _Question:_ can any \(3\)-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) be extended to a proper \(3\)-coloring of \(G\)? **Complexity:**\(\Pi^{\mathrm{P}}_{2}[*k*]\)-complete [7; 41]. 3-Coloring-Extension(#uncol.leaves)

_Instance:_ a graph \(G=(V,E)\) with \(n\) many leaves, and an integer \(m\). _Parameter:_\(n-m\). _Question:_ can any 3-coloring that assigns a color to exactly \(m\) leaves of \(G\) (and to no other vertices) be extended to a proper 3-coloring of \(G\)? **Complexity:** para-\(\Pi^{\mathsf{P}}_{2}\)-complete [7; 41]. ## 6 Other Problems

### First-Order Logic Model Checking

First-order logic model checking is at the basis of a well-known hardness theory in parameterized complexity theory [22]. The following problem, also based on first-order logic model checking, offers another characterization of the parameterized complexity class \(\Sigma^{\mathsf{P}}_{2}[k*]\). We introduce a few notions that we need for defining the model checking perspective on \(\Sigma^{\mathsf{P}}_{2}[k*]\). A _(relational) vocabulary_\(\tau\) is a finite set of relation symbols. Each relation symbol \(R\) has an _arity_\(\operatorname{arity}(R)\geq 1\). A _structure_\(\mathcal{A}\) of vocabulary \(\tau\), or \(\tau\)_-structure_ (or simply _structure_), consists of a set \(A\) called the _domain_ and an interpretation \(R^{\mathcal{A}}\subseteq A^{\operatorname{arity}(R)}\) for each relation symbol \(R\in\tau\).