## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
Moreover, we say that \(x\in X(\vec{v})\setminus X(\vec{u})\) has been \(X\)-illegally removed at \(\vec{u}\) if there is some \(U\in\mathbb{E}(\vec{u})\) such that \(x\in X(U)\)._

**Definition 9**. : _We call a table \(\tau\) augmentable if the following conditions hold:_

1. _For all rows of the form_ \(\langle M,\,\cdots,\mathcal{C}\rangle\)_, we have_ \(\mathcal{C}=\emptyset\)_._
2. _For all_ \(\vec{u},\vec{u}_{s}.\in\tau\) _with_ \(\vec{u}\
eq\vec{u}\) _it holds that_ \(\alpha(\vec{u})\cup\beta(\vec{u})\
eq\alpha(\vec{v})\cup\beta(v)\)_._
3. _For all_ \(\vec{u}=\langle M,\sigma,\cdots\rangle\in\tau\)_,_ \(\{\{\vec{u}_{1}^{\prime}\},\ldots,\{\vec{u}_{k}^{\prime}\}\}\in\text{orig}_{t }(\vec{u})\)_,_ \(1\leq i<j\leq k\)_,_ \(I\in\mathbb{E}(\vec{u}_{i}^{\prime})\) _and_ \(J\in\mathbb{E}(\vec{u}_{j}^{\prime})\) _it holds that_ \(\alpha^{*}(I)\cap\alpha^{*}(I)\subseteq M\) _and_ \(\beta^{*}(I)\cap\beta^{*}(J)\subseteq\sigma\)_._
4. _No element of_ \(\alpha^{*}(\tau)\) _has been_ \(\alpha\)_-illegally introduced and no element of_ \(\beta^{*}(\tau)\) _has been_ \(\beta\)_-illegally introduced._
5. _No element of_ \(\alpha^{*}(\tau)\) _has been_ \(\alpha\)_-illegally removed and no element of_ \(\beta^{*}(\tau)\) _has been_ \(\beta\)_-illegally removed._

_call \(\mathbb{W}\text{-Tabs}\) augmentable if all its tables are augmentable._

It is easy to see that \(\mathbb{MOD}\text{-Tabs}\) are augmentable, that is, Algorithm 2 (\(\texttt{DP}_{\text{MOD}}(\cdot)\)) computes only augmentable tables. **Observation 3**. : \(\mathbb{MOD}\text{-Tabs}\) _are augmentable, since \(\texttt{DP}_{\text{MOD}}(\cdot)\) computes augmentable tables. \(\mathbb{CMOD}\text{-Tabs}\) are augmentable, since \(\texttt{DP}_{\text{CMOD}}(\cdot)\) computes augmentable tables._

The following theorem establishes that we can reduce an instance of EnumAsp (restricted to disjunctive input programs) when parameterized by semi-incidence treewidth to an instance of EnumMinSAT1 when parameterized by the treewidth of its incidence graph. **Lemma 4**. : _Given a disjunctive program \(P\) of semi-incidence treewidth \(k=\text{tw}(S(P))\). We can produce in time \(\mathcal{O}(\|P\|)\) a propositional formula \(F\) such that the treewidth \(k^{\prime}\) of the incidence graph \(I(F)\) (the incidence graph \(I(F)\) of a propositional formula \(F\) in CNF is the bipartite graph that has the variables and clauses of \(F\) as vertices and an edge \(v\) c if \(v\) is a variable that occurs in \(c\) for some clause \(c\in F\)[32]. )T is \(k^{\prime}\leq 7k+2\) and the answer sets of \(P\) and subset-minimal models of \(F^{*}\) are in a particular one-to-one correspondence. More precisely, \(M\) is an answer set of \(P\) if and only if \(M\cup M_{aux}\cup\{sol\}\) is a subset-minimal model of \(F\) where \(M_{aux}\) is a set of additional variables occurring in \(F\), but not in \(P\) and variables introduced by Tseitin normalization._

Proof. : Let \(P\) be a disjunctive program of semi-incidence treewidth \(k=\mathit{tw}(S(P))\). First, we construct a formula \(F\) consisting of a conjunction over formulas \(F^{\mathrm{r}}\), \(F^{\mathrm{impl}}\), \(F^{\mathrm{sol}}\), \(F^{\mathrm{min}}\) followed by Tseitin normalization of \(F\) to obtain \(F^{*}\). Among the atoms (Note that we do not distinguish between atoms and propositional variables in terminology here.) of our formulas will the atoms \(\mathrm{at}(P)\) of the program. Further, for each atom \(a\) such that \(a\in B^{-}(r)\) for some rule \(r\in P\), we introduce a fresh atom \(a^{\prime}\). In the following, we denote by \(Z^{\prime}\) the set \(\{z^{\prime}:z\in Z\}\) for any set \(Z\) and by \(B^{-}_{P}:=\bigcup_{r\in P}B^{-}_{P}\). Hence, \((B^{-}_{P})^{\prime}\) denotes a set of fresh atoms for atoms occurring in any negative body.