## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
From a theoretical perspective, our novel algorithm \(\mathsf{M\text{-}DP_{SINC}}\) is multi-variate practically, considering treewidth together with the maximum number of witnesses in a table that lead to a solution at the root. Intuitively, this subtle difference can yield practical advantages, especially if the number of relevant witnesses in a table that lead to a solution is subexponential in the treewidth. Therefore, our novel algorithm is designed to allow for an early cleanup (purging) of witnesses that do not lead to answer sets, which in consequence (i) avoids to construct expendable counter-witnesses. Moreover, multiple traversals enable us to store witnesses and counter-witnesses separately, which in turn (ii) avoids storing counter-witnesses duplicately and (iii) allows for highly space efficient data structures (pointers) in practice when linking witnesses and counter-witnesses together. Figure 4 (right, middle) presents the control flow of the new multi-traversal approach \(DynASP2.5\), where \(\mathsf{M\text{-}DP_{SINC}}\) introduces a much more elaborate computation in Step 3. ### The Algorithm

Our algorithm (\(\mathsf{M\text{-}DP_{SINC}}\)) executed as Step 3 runs \(\mathsf{DP_{MOD}}\), \(\mathsf{DP_{CMOD}}\) and \(\mathsf{DPL_{MOD}}\),\(\mathsf{CMOD}\) in three traversals (3.1, 3.2, and 3.3) as follows:

1. First, we run the algorithm \(\mathsf{DP_{MOD}}\), which computes in a bottom-up traversal for every node \(t\) in the tree decomposition a table \(\mathsf{MOD}\)-\(\text{Tabs}[t]\) of witnesses for \(t\). Then, in a top-down traversal for every node \(t\) in the TD remove from tables \(\mathsf{MOD}\)-\(\text{Tabs}[t]\) witnesses, which do not extend to a witness in the table for the parent node (\"Purge non-witnesses\"); these witnesses can never be used to construct a model (nor answer set) of the program. 2. For this step, let \(\mathsf{CMOD}\) be a table algorithm computing only counter-witnesses of \(\mathsf{SINC}\) (blue parts of Algorithm 2). We execute \(\mathsf{DP_{CMOD}}\), for all witnesses, compute counter-witnesses at once and store the resulting tables in \(\mathsf{CMOD}\)-\(\text{Tabs}[\cdot]\). For every node \(t\), table \(\mathsf{CMOD}\)-\(\text{Tabs}[t]\) contains counter-witnesses to witness being \(\subset\)-minimal. Again, irrelevant rows are removed (\"Purge non-counter-witnesses\"). 3. Finally, in a bottom-up traversal for every node \(t\) in the TD, witnesses and counter-witnesses are linked using algorithm \(\mathsf{DPL_{MOD}}\),\(\mathsf{CMOD}\) (see Algorithm 3). \(\mathsf{DPL_{MOD}}\),\(\mathsf{CMOD}\) takes previous results and maps rows in \(\mathsf{MOD}\)-\(\text{Tabs}[t]\) to a table (set) of rows in \(\mathsf{CMOD}\)-\(\text{Tabs}[t]\). We already explained the table algorithms \(\mathsf{DP_{MOD}}\) and \(\mathsf{DP_{CMOD}}\) in the previous section. The main part of our multi-traversal algorithm is the algorithm \(\mathsf{DPL_{MOD}}\),\(\mathsf{CMOD}\) based on the general algorithm \(\mathsf{DPL_{W,C}}\) (Algorithm 3) with \(\mathbb{W}=\mathsf{MOD}\), \(\mathbb{C}=\mathsf{CMOD}\), which links those separate tables together. Before we quickly discuss the core of \(\mathsf{DPL_{W,C}}\) in Lines 6-10, note that Lines 3-5 introduce auxiliary definitions. Line 3 combines rows of the child

Figure 4: Control flow for DP-based ASP solver (DynASP2, **left**) and for DynASP2.5 (**right**). nodes of given node \(t\), which is achieved by a product over sets, where we drop the order and keep sets only. Line 4 concerns determining for a row \(\vec{u}\) its _origins_ (finding preceding combined rows that lead to \(\vec{u}\) using table algorithm \(\mathbb{W}\)). Line 5 covers deriving succeeding rows for a certain child row combination its _evolution_ rows via algorithm \(\mathbb{C}\). In an implementation, origin as well as evolution are not computed, but represented via pointer data structures directly linking to \(\mathbb{W}\)-Tabs\([\cdot]\) or \(\mathbb{C}\)-Tabs\([\cdot]\), respectively.