## 3 A Single Traversal DP Algorithm
#### An Algorithm on the Semi-Incidence Graph
While DynASP2.5 (M-DP\({}_{\text{SINC}}\)) does not take additional TD features into account, we also implemented a variant (_DynASP2.5 degraph_), which prefers one out of ten TDs that intuitively speaking avoids to introduce head atoms of some rule \(r\) in node \(t\), without having encountered every body atom of \(r\) below \(t\), similar to atom dependencies in the program [34]. The variant _DynASP2.5 joinsize_ minimizes bag sizes of child nodes of join nodes, c.f. [18]. ### Benchmark Set

In the following empirical evaluation, we consider the uniform Steiner tree problem (ST), which is a variant of a decision problem among the first well-known NP-hard problems [35]. We take public transport networks as input graphs. The instance graphs have been extracted from publicly available mass transit data feeds and split by transportation type, e.g., train, metro, tram, combinations [36]. We heuristically computed tree decompositions [18] and obtained decompositions of small width relatively fast unless detailed bus networks were present. Among the graphs considered were public transit networks of the cities London, Bangladesh, Timisoara, and Paris. Benchmarks, encodings, and results are available online at [[https://github.com/daajoe/dynasp_experiments/tree/ipec2017](https://github.com/daajoe/dynasp_experiments/tree/ipec2017)]([https://github.com/daajoe/dynasp_experiments/tree/ipec2017](https://github.com/daajoe/dynasp_experiments/tree/ipec2017)). We assumed for simplicity, that edges have unit costs, and randomly generated a set of terminals. #### 5.2.1 Steiner Tree Problem

The considered version of the uniform Steiner tree problem can be formalized as follows:

**Definition 11** (Uniform Steiner Tree Problem (St)). : _Let \(G=(V,E)\) be a graph and \(V_{T}\subseteq V\) be a set of vertices, called terminal vertices. Then, a uniform Steiner tree on \(G\) is a tree \(S_{G}=(V_{S},E_{S})\) with \(V_{S}\subseteq V\) and \(E_{S}\subseteq E\) such that_

1. _all terminal vertices are covered:_ \(V_{T}\subseteq V_{S}\)_, and_
2. _the number of edges in_ \(E_{S}\) _forms a minimum: there is no tree, where all terminal vertices are covered that consists of no more than_ \(|E_{S}|-1\) _many edges._

_The uniform Steiner tree problem (St) asks to compute the uniform Steiner trees for \(G\) and \(V_{T}\)._

**Example 6** (Encoding St into an ASP program). : _Let \(G=(V,E)\) be a graph and \(V_{T}\subseteq V\) be a set of terminal vertices. We encode the problem St into an ASP program as follows: Among the atoms of our program will be an atom \(a_{v}\) for each vertex \(v\in V_{T}\), and an atom \(e_{vw}\) for each edge \(vw\in E\) assuming \(v<w\) for an arbitrary, but fixed total ordering \(<\)\(\sim\)\(v\). Let \(s\) be an arbitrary vertex \(s\in V_{T}\). We generate program \(P(G,V_{T}):=\{\{e_{vw}\}\leftarrow\ ;\ \sim e_{vw}\ |\ vw\in E\}\cup\{a_{v} \leftarrow\ a_{w},e_{vw};\ a_{w}\leftarrow\ a_{v},e_{vw}\ |\ vw\in E,vs.<w\}\cup\{\leftarrow\
eg a_{v}\ |\ \vs.\in V_{T}\}\cup\{a_{s} \leftarrow\}\). It is easy to see that the answer sets of the program and the uniform Steiner trees are in a one-to-one correspondence._

#### 5.2.2 Considered Encodings

We provide the encoding as non-ground ASP program, which allows to state first-order variables that are instantiated by present constants. This allows us to provide a readable encoding and avoid stating an encoder as an imperative program. Note that for certain non-ground programs, treewidth guarantees are known [37]. In the experiment, we used _gringo_[38] as grounder. An encoding for the problem St is depicted in Listing 1 and assumes a specification of the graph (via _edge_) and the terminal vertices (_terminalVertex_) as well as the number (_numVertices_) of vertices. Note that this encoding is quite compact and non-ground and therefore it contains first-order variables. Prior to solving, these first-order variables are instantiated by a grounder, which results in a ground program.