## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
Since \(u\) is a local partial solution, there exists a partial solution \(\hat{u}=(\hat{M},\hat{\sigma},\hat{\mathcal{C}})\) for node \(t\), satisfying the conditions of Definition 5. Since \(r\) is the removed rule, we have \(r\in\hat{\sigma}\). By similar arguments, we have \(r\in\hat{\rho}\) for any tuple \((\hat{\mathcal{C}},\hat{\rho})\in\hat{\mathcal{C}}\). Hence, \(\hat{u}\) is also a partial solution for \(t^{\prime}\) and we define \(u^{\prime}:=\hat{u}^{\prime}\), which is the projection of \(\hat{u}\) onto the bag of \(t^{\prime}\). Apparently, the tuple \(u^{\prime}\) is a local partial solution for node \(t^{\prime}\) according to Definition 5. Then, \(u\) can be derived using \(\mathbb{SINC}\) algorithm and \(u^{\prime}\). By similar arguments, we establish the lemma for \(a\in\operatorname{at}_{t^{\prime}}\setminus\operatorname{at}_{t}\) and the remaining (three) node types. Hence, the lemma sustains. Now, we are in situation to prove the correctness statement in Proposition 1. Proof of Proposition 1 (Correctness). : We first show soundness. Let \(\mathcal{T}=(T,\chi)\) be the given tree decomposition, where \(T=(N,\cdot,n)\). By Observation 2 we know that there is an answer set for \(P\) if and only if there exists a local partial solution for the root \(n\). Note that the tuple is of the form \(\langle\emptyset,\emptyset,\emptyset\rangle\) by construction. Hence, we proceed by induction starting from the leaf nodes. In fact, the tuple \(\langle\emptyset,\emptyset,\emptyset\rangle\) is trivially a partial solution by Definitions 3 and 4 and also a local partial solution of \(\langle\emptyset,\emptyset,\emptyset\rangle\) by Definition 5. We already established the induction step in Lemma 1. Hence, when we reach the root \(n\), when traversing the tree decomposition in post-order by algorithm \(\operatorname{\mathtt{DP}_{SINC}}\), we obtain only valid tuples in between and a tuple of the form \(\langle\emptyset,\emptyset,\emptyset\rangle\) in the table of the root \(n\) witnesses an answer set. Next, we establish completeness by induction starting from the root \(n\). Let therefore, \(M\) be an arbitrary answer set of \(P\). By Observation 1, we know that for the root \(n\) there exists a local partial solution of the form \(\langle\emptyset,\emptyset,\emptyset\rangle\) for partial solution \(\langle M,\sigma,\emptyset\rangle\) with \(r\in\sigma\) for \(r\in P\). We already established the induction step in Lemma 2. Hence, we obtain some (corresponding) tuples for every node \(t\). Finally, stopping at the leaves \(n\). In consequence, we have shown both soundness and completeness resulting in the fact that the correctness statement made in Proposition 1 is true. Next, we turn our attention to the worst-case runtime bounds claimed in Proposition 1. First, we give a lemma on worst-case space requirements in tables for the nodes of our algorithm. Lemma 3: _Given a program \(P\), a tree decomposition \(\mathcal{T}=(T,\chi)\) with \(T=(N,\cdot,\cdot)\) of the semi-incidence graph \(S(P)\), and a node \(t\in N\). Then, there are at most \(2^{k+1}\cdot 2^{k+1}\cdot 2^{2^{k+1}\cdot 2^{k+1}}\) tuples in \(\tau_{t}\) using algorithm \(\operatorname{\mathtt{DP}_{SINC}}\) for width \(k\) of \(\mathcal{T}\)._

Proof (Sketch). : Let \(P\) be the given program, \(\mathcal{T}=(T,\chi)\) a tree decomposition of the semi-incidence graph \(S(P)\), where \(T=(N,\cdot,\cdot)\), and \(t\in N\) a node of the tree decomposition. Then, by definition of a decomposition of the primal graph for each node \(t\in N\), we have \(|\chi(t)|-1\leq k\). In consequence, we can have at most \(2^{k+1}\) many witnesses, and for each witness a subset of the set of witnesses consisting of at most \(2^{2^{k+1}}\) many counter-witnesses. In total, we need to distinguish \(2^{k+1}\) two states for the sat-states \(\sigma\) and for each witness of a tuple in the table \(\tau_{t}\) for node \(t\).