## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
: The proof follows previous work [17]. We sketch only differences from their work. Any row \(\vec{u}\in\tau\) of any table \(\tau\) not only consists of set \(\alpha(\vec{u})\) being subject to subset-minimization and relevant to solving Enumasp. In addition, our definitions presented above also allow _\"auxiliary\"_ sets \(\beta(\vec{u})\) per row \(\vec{u}\), which are not subject to the minimization. Moreover, by the correctness of the table algorithm \(\mathbb{SINC}\) above, we only require to store a set \(\mathcal{C}\) of counter-witnesses \(\langle C,\cdots\rangle\in\mathcal{C}\) per witness set \(M\), where each \(C\) forms a _strictly_\(\subset\)-smaller model of \(M\). As a consequence, there is no need to differ between sets of counter-witnesses, which are strictly included or not, see [17]. Finally, we do not need to care about duplicate rows (solved via compression function \(\mathit{compr}(\cdot)\) in [17]) in \(\tau\), since \(\tau\) is a set. Theorem 4.2:EnumAsp _when the input is restricted to disjunctive programs can be solved in time \(2^{2^{(\mathbb{P}_{M\!\! ## 5 Experimental Evaluation

### Implementation Details

Efficient implementations of dynamic programming algorithms on TDs are not a by-product of computational complexity theory and involve tuning and sophisticated algorithm engineering. Therefore, we present additional implementation details of algorithm M-DP\({}_{\text{SINC}}\) into our prototypical multi-traversal solver DynASP2.5, including two variations (depgraph, joinsize TDs). Even though one can construct a nice TD from a TD without increasing its width, one may artificially introduce additional atoms in a nice TD. This results in several additional intermediate join nodes among such artificially introduced atoms requiring a significant amount of total unnecessary computation in practice. On that account, we use tree decompositions that do _not_ have to be _nice_. In order to still obtain a fixed-parameter linear algorithm, we limit the number of children per node to a constant. Moreover, _linking_ counter-witnesses to witnesses efficiently is crucial. The main challenge is to deal with situations where a row (witness) might be linked to different set of counter-witnesses depending on different predecessors of the row (hidden in set notation of the last line in Algorithm 3). In these cases, DynASP2.5 eagerly creates a \"clone\" in form of a very light-weighted proxy to the original row and ensures that only the original row (if at all required) serves as counter-witness during traversal three. Together with efficient caches of counter-witnesses, DynASP2.5 reduces overhead due to clones in practice. Dedicated _data structures_ are vital. Sets of witnesses and satisfied rules are represented in the DynASP2.5 system via constant-size bit vectors. 32-bit integers are used to represent by value 1 whether an atom is set to true or a rule is satisfied in the respective bit positions according to the bag. A restriction to 32-bit integers seems reasonable as we assume for now (practical memory limitations) that our approach works well on TDs of width \(\leq\) 20. Since state-of-the-art computers handle such constant-sized integers extremely efficient, DynASP2.5 allows for efficient projections and joins of rows, and subset checks in general. In order to not recompute counter-witnesses (in Traversal 3.II) for different witnesses, we use a three-valued notation of counter-witness sets consisting of atoms set to true (T) or false (F) or false but true in the witness set (TW) used to build the reduct. Note that the algorithm enforces that only (TW)-atoms are relevant, i.e., an atom has to occur in a default negation or choice rule. Minimum width is not the only optimization goal when computing TDs by means of heuristics. Instead, using TDs where a certain feature value has been maximized in addition (_customized TDs_) works seemingly well in practice [12; 33].