Visualization of Event Graphs for Train Schedules

Note that the number of turns in a time-space diagram is determined solely by the function $y$ which represents an ordering of the locations. Therefore, Turn Minimization is closely related to the following problem.

In fact, there is a straightforward translation that transforms optimal solutions of Turn Minimization to optimal solutions of Maximum Betweenness and vice versa. However, note that the objective functions of these problems differ. In Turn Minimization we minimize the number of turns, which corresponds to minimizing the number of unsatisfied restrictions in Maximum Betweenness.

Maximum Betweenness and other slightly modified variants have been studied extensively [17, 18, 7, 19, 6, 5] mainly motivated by applications in biology. In particular, Opatrny showed that Maximum Betweenness is $\mathrm{𝖭𝖯}$-hard [16]. Further, the problem admits 1/2-approximation algorithms [4, 13], but for any $\epsilon >0$ it is $\mathrm{𝖭𝖯}$-hard to compute a $(1/2+\epsilon )$-approximation [1].

Several exact algorithms have been proposed. There is an intuitive integer linear program formulation that uses linear orderings. This formulation has been used in various variants and algorithms as a baseline before [6, 5]. We state this formulation in Section 5 since we also use this formulation as a starting point. Note that this formulation requires $𝒪({|S|}^3)$ many constraints due the transitivity constraints for the linear ordering and the fact that there can be $𝒪({|S|}^3)$ many restrictions. This may result in long computation times. Since applications in biology often deal with a large number of restrictions, improvements of this formulation have been made via cutting-plane approaches that target the transitivity and the restriction constraints using the trivial lifting technique²²2Here: complete linear descriptions of smaller instances $(S,R)$ are used to generate valid inequalities for larger instances $(S^{\prime },R^{\prime })$ where $S\subseteq S^{\prime }$, $R\subseteq R^{\prime }$. [6, 5]. To overcome the issue of a cubic number of transitivity constraints, a mixed-integer linear program has been proposed [19] that circumvents the large number of constraints entirely by modelling a linear ordering with continuous variables that are required to be distinct. As a consequence, this formulation runs faster than the intuitive formulation. However, this program requires a user-specified parameter that influences the runtime significantly and is not obvious to choose.

Note that due to the relationship between Turn Minimization and Maximum Betweenness, exact algorithmic approaches for one of the problems can be directly transferred to the other, while approximation guarantees cannot. However, most of the algorithmic approaches for Maximum Betweenness are optimized for instances where the ratio between $|R|$ and $|S|$ is large, while this ratio is only moderate in our setting. As a result, in our setting, the transitivity constraints become the bottleneck as opposed to the constraints that model the restrictions in $R$. Another notable difference is that in Turn Minimization we have access to additional information on the relations between restrictions (the train lines). We strive to leverage these differences to develop new approaches. In particular, we consider the case that instances admit drawings with a small number of turns (as otherwise a drawing would not be comprehensible). Further, we consider the case that the underlying infrastructure of the event graph is sparse (as this is common in train infrastructure).

First, we consider Turn Minimization from a (parameterized) complexity theoretic perspective; see Section 3. In particular, we show that it is $\mathrm{𝖭𝖯}$-hard to compute an $\alpha$-approximation for any constant $\alpha \ge 1$ and that the problem is $\mathrm{𝗉𝖺𝗋𝖺}\text{-}\mathrm{𝖭𝖯}$-hard when parameterized by the number of turns. The problem is also $\mathrm{𝗉𝖺𝗋𝖺}\text{-}\mathrm{𝖭𝖯}$-hard when parameterized by the vertex cover number of the location graph, a graph that represents the infrastructure. Second, we propose a preprocessing strategy that reduces a given event graph $ℰ$ into a smaller event graph ${ℰ}^{\prime }$ that admits drawings with the same number of turns; see Section 4. Third, we refine the intuitive integer linear program in two different ways; see Section 5. The first refinement is a simple cutting-plane approach that iteratively adds transitivity constraints until a valid (optimal) solution is found. The second refinement uses a tree decomposition to find a light-weight formulation of the problem. We conclude with an experimental analysis and future work in Sections 6 and 7. While the preprocessing strategy cannot be easily translated to the Maximum Betweenness problem, our remaining results carry over.

Intuitively, a tree decomposition is a decomposition of a graph $G$ into a tree $T$ which gives structural information about the separability of $G$. The treewidth of a graph $G$ is a measure that captures how similar a graph $G$ is to a tree. For instance, every tree has treewidth 1, the graph of a $(k\times k)$-grid has treewidth $k$, and the treewidth of the complete graph $K_n$ is $n-1$. More formally, a tree decomposition $𝒯=(T,{\{X_t\}}_{t\in V(T)})$ of $G$ consists of a tree $T$ and, for each node $t$ of $T$, of a subset $X_t$ of $V(G)$ called bag such that (see Figure 3 for an example):

1. (T1)

   the union of all bags is $V(G)$,

2. (T2)

   for every edge $\{u,v\}$ of $G$, the tree $T$ contains a node $t$ such that $\{u,v\}\subseteq X_t$, and

3. (T3)

   for every vertex $v$ of $G$, the nodes whose bags contain $v$ induce a connected subgraph of $T$.

The width of a tree decomposition is defined as $\max \{|X_t|:t\in V(T)\}-1$; for example, the tree decomposition in Figure 3 has width 2. The treewidth of a graph $G$, $\mathrm{tw}(G)$, is the smallest value such that $G$ admits a tree decomposition of this width. Any tree decomposition $(T,{\{X_t\}}_{t\in V(T)})$ has the following properties.

1. (P1)

   For every edge $\{a,b\}$ of $T$, the graph $T-\{a,b\}$ has two connected components $T_a$ and $T_b$, where $T_a$ contains $a$ and $T_b$ contains $b$. They induce a separation $(A,B)=({\bigcup }_{t\in V(T_a)}{X}_t,{\bigcup }_{t\in V(T_b)}{X}_t)$ of $G$ with separator $X_a\cap X_b$. In particular, $A\cap B=X_a\cap X_b$, and $G$ does not contain any edge between a vertex in $A\setminus X_a$ and a vertex in $B\setminus X_b$.

2. (P2)

   For every clique $K$ of $G$, the tree $T$ contains a node $t$ such that $V(K)\subseteq X_t$.

For every triplet of consecutive events, the corresponding locations form a triangle in ${ℒ}^{\prime }$. Hence, due to Property (P2), in any tree decomposition of ${ℒ}^{\prime }$, there is a bag that contains the three locations. Thus, every potential turn occurs in at least one bag, and it suffices to run a standard dynamic program over a (nice) tree decomposition of ${ℒ}^{\prime }$. $◀$

Note that this result might not be practical since the treewidth of the augmented location graph might be considerably larger than the treewidth of the location graph.

Let $k$ be the number of turns in a turn-optimal drawing $\mathrm{\Gamma }$ of an event graph $ℰ$ and let $k^{\prime }$ be the number of turns in a turn-optimal drawing ${\mathrm{\Gamma }}^{\prime }$ of an event graph $ℰ$ after Reduction Rule 1 was applied on the contractible transit component $C$. Further, for the sake of simplicity, assume that any train traversing $C$ traverses $C$ only once. If a train $z$ traverses $C$ multiple times, the same arguments apply for each connected component of the train line of $z$ going through $C$. Note that this can indeed happen (if the event graph represents a schedule that contains a train that moves through $C$ periodically).

Without increasing the number of turns, we now transform ${\mathrm{\Gamma }}^{\prime }$ into a drawing of $ℰ$ that contains $C$, as follows. Let $\{s,t\}$ be the pair that separates $C$ from $ℒ\setminus C$. Let $y^{\prime }(s)$ and $y^{\prime }(t)$ be the levels of $s$ and $t$ in ${\mathrm{\Gamma }}^{\prime }$, respectively. Without loss of generality, assume that . Since $C$ is contractible, $C$ admits an acyclic (topological) ordering of the locations in $C$ such that the train line of every train traversing $C$ is directed from $s$ to $t$. Let ${\prec }_C$ be such an ordering and let $z$ be a train traversing $C$, where $z^{\prime }=⟨v_1,\mathrm{\dots },v_j⟩$ is the component of the train line of $z$ that traverses $C$ such that $\mathrm{\ell }(v_1)=s$ and $\mathrm{\ell }(v_j)=t$. Since ${\prec }_C$ is a valid acyclic topological ordering, it holds that $\mathrm{\ell }(v_i){\prec }_C\mathrm{\ell }(v_{i+1})$ for each . Thus, by extending $y^{\prime }$ so that each vertex $p$ in $C$ is assigned a level $y^{\prime }(p)\in ]y{}^{\prime }(s),y{}^{\prime }(t)[$, with $p,q\in V(C)$ and if and only if $p{\prec }_{C}q$, no additional turns are introduced in the transformed drawing. As a result, we obtain a drawing of $ℰ$ that contains $C$ and has the same number of turns as ${\mathrm{\Gamma }}^{\prime }$. Hence $k\le k^{\prime }$.

Conversely, we transform $\mathrm{\Gamma }$ into a drawing with at most $k$ turns where the component $C$ is contracted. Let $\{s,t\}$ be the pair that separates $C$ from $ℒ\setminus C$. Let $y(s)$ and $y(t)$ be the levels of $s$ and $t$ in $\mathrm{\Gamma }$. Without loss of generality, . First, assume that for each $p\in V(C)$ it holds that . Then, contracting $C$ into a single edge transforms $\mathrm{\Gamma }$ into a drawing of the reduced instance with at most $k$ turns. Now, let $L\subseteq V(C)$ be the set of vertices below $s$, and let $U\subseteq V(C)$ be the set of vertices above $t$. We describe only how to handle $U$ since $L$ can be handled analogously. Let $\mathrm{\Delta }$ be the number of train lines with at least one vertex in $U$. We reorder the levels of the vertices in $U$ according to a topological ordering of $C$ restricted to $U$ and move all vertices in $U$ such that their levels are between $y(t)$ and . Each train line with at least one vertex in $U$ corresponds to at least one turn in $U$, namely a turn at the vertex of a train line with the largest level. Therefore, moving and reordering $U$ removes at least $\mathrm{\Delta }$ turns. Also, the movement and reordering of $U$ results in at most $\mathrm{\Delta }$ turns more at $t$ since the only vertices that were moved are vertices in $U$. After moving and reordering $U$ and $L$, we are in the first case and can hence contract $C$. Summing up, we can transform a turn-optimal drawing $\mathrm{\Gamma }$ of an event graph $ℰ$ into a drawing with a contracted component $C$ without changing the number of turns, implying that $k^{\prime }\le k$.

We conclude that Reduction Rule 1 is sound. $◀$

Note that we can apply Reduction Rule 1 exhaustively in cubic time (in the number of vertices and edges of $ℒ$ and $ℰ$): we iterate over all (up to $𝒪({|V(ℒ)|}^2)$ many) separating pairs and contract each connected component with respect to the current pair, if possible. Below we show that, using two data structures, we can speed up the application of Reduction Rule 1 considerably.

A block-cut tree represents a decomposition of a graph into maximal biconnected components (called blocks) and cut vertices. Given a graph $G$, let $𝒞$ be the set of cut vertices of $G$, and let $ℬ$ be the set of blocks of $G$. Note that two blocks share at most one vertex with each other, namely a cut vertex. The block-cut tree ${𝒯}_{\mathrm{bc}}$ of $G$ (see Figure 4 for an example) has a node for each element of $ℬ\cup 𝒞$ and an edge between $b\in ℬ$ and $c\in 𝒞$ if and only if $c$ is contained in the component represented by $b$. Note that the leaves of a block-cut tree are $ℬ$-nodes. For example, the block-cut tree of a biconnected graph is a single node. The block-cut tree of an $n$-vertex path is itself a path, with $2n-3$ nodes.

If a graph $G$ is biconnected, an SPQR-tree represents the decomposition of $G$ into its triconnected components via separating pairs, where S (series), P (parallel), Q (a single edge), and R (remaining or rigid) stand for the different node types of the tree that represent how the triconnected components compose $G$. An SPQR-tree represents all planar embeddings of a graph. Therefore, SPQR-trees are widely used in graph drawing and beyond [15]. SPQR-trees are defined in several ways in the literature. Here, we recall the definition of Gutwenger and Mutzel [10], which is based on an earlier definition of Di Battista and Tamassia [2].

Let $G$ be a multi-graph. A split pair is either a separating pair or a pair of adjacent vertices. A split component of a split pair $\{u,v\}$ is either an edge $\{u,v\}$ or a maximal subgraph $C$ (containing $\{u,v\}$) of $G$ such that $\{u,v\}$ is not a split pair of $C$. Let $\{s,t\}$ be a split pair of $G$. A maximal split pair $\{u,v\}$ of $G$ with respect to $\{s,t\}$ is a pair such that, for any other split pair $\{u^{\prime },v^{\prime }\}$, the vertices $u$, $v$, $s$, and $t$ are in the same split component. Let $e=\{s,t\}$ be an edge of $G$ called reference edge. The SPQR-tree ${𝒯}_{\mathrm{spqr}}$ of $G$ with respect to $e$ is a rooted tree whose nodes are of four types: S, P, Q, and R. Each node $\mu$ of ${𝒯}_{\mathrm{spqr}}$ has an associated biconnected multi-graph called the skeleton of $\mu$. Every vertex in a skeleton corresponds to a vertex in $G$ and every edge $\{u,v\}$ in a skeleton corresponds to a child of $\mu$ that represents a split component of $G$ that is separated by $\{u,v\}$. The tree ${𝒯}_{\mathrm{spqr}}$ is recursively defined as follows (see Figure 5 for an example):

Trivial Case:

If $G$ consists of exactly two parallel edges between $s$ and $t$, then ${𝒯}_{\mathrm{spqr}}$ consists of a single Q-node whose skeleton is $G$ itself.

Parallel Case:

If the split pair $\{s,t\}$ has at least three split components $G_1,\mathrm{\dots },G_k$, the root of ${𝒯}_{\mathrm{spqr}}$ is a P-node $\mu$ whose skeleton consists of $k$ parallel edges $e_1,\mathrm{\dots },e_k$ between $s$ and $t$.

Series Case:

If the split pair $\{s,t\}$ has exactly two split components, one of them is $e$, and the other is denoted with $G^{\prime }$. If $G^{\prime }$ has cut vertices $c_1,\mathrm{\dots },c_{k-1}$ ($k\ge 2$) that partition $G$ into its blocks $G_1,\mathrm{\dots },G_k$, in this order from $s$ to $t$, the root of ${𝒯}_{\mathrm{spqr}}$ is an S-node $\mu$ whose skeleton is the cycle $e_0,e_1,\mathrm{\dots },e_k$, where $e_0=e$, $c_0=s$, $c_k=t$, and $e_i=(c_{i-1},c_i)$ for $i=1,\mathrm{\dots },k$.

Rigid Case:

If none of the above cases applies, let $\{s_1,t_1\},\mathrm{\dots },\{s_k,t_k\}$ be the maximal split pairs of $G$ with respect to $\{s,t\}$ and let $G_i$ ($i=1,\mathrm{\dots },k$) be the union of all the split components of $\{s_i,t_i\}$ but the one containing $e$. The root of ${𝒯}_{\mathrm{spqr}}$ is an R-node whose skeleton is obtained from $G$ by replacing each subgraph $G_i$ with the edge $e_i=\{s_i,t_i\}$.

Except for the trivial case, every node $\mu$ of ${𝒯}_{\mathrm{spqr}}$ has children ${\mu }_1,\mathrm{\dots },{\mu }_k$ such that ${\mu }_i$ is the root of the SPQR-tree of $G_i\cup e_i$ with respect to $e_i$. The reference edge $e$ is represented by a Q-node which is the root of ${𝒯}_{\mathrm{spqr}}$. Each edge $e_i$ in the skeleton of $\mu$ is associated with the child ${\mu }_i$ of $\mu$. This edge is also present in ${\mu }_i$ and is called virtual edge in ${\mu }_i$. The endpoints of edge $e_i$ are called poles of the node ${\mu }_i$. The pertinent graph $G_{\mu }$ of $\mu$ is the subgraph of $G$ that corresponds to the real edges (Q-nodes) in the subtree rooted at $\mu$.

Let $ℒ$ be the connected location graph of an event graph $ℰ$. If the location graph is not connected we can apply the algorithm on every connected component of $ℒ$. We consider the case where $ℒ$ is not biconnected as this case also handles the biconnected subgraphs of $ℒ$ and can therefore easily be adapted for the case where $ℒ$ is biconnected. We start by decomposing $ℒ$ into a block-cut tree ${𝒯}_{\mathrm{bc}}$ with vertex set $ℬ\cup 𝒞$. For every block $b$ in $ℬ$ we do the following. We construct an SPQR-tree ${𝒯}_{\mathrm{spqr}}^b$ of the biconnected component corresponding to the block $b$ and temporarily mark all cut vertices of $𝒞$ contained in $b$ as terminal in $b$ so that no cut vertex can be contracted while we process ${𝒯}_{\mathrm{spqr}}^b$. Let ${\mu }_r$ be the root of ${𝒯}_{\mathrm{spqr}}^b$ and let ${ℰ}_{\mu }$ be the event graph that corresponds to the pertinent graph ${ℒ}_{\mu }$ for a node $\mu$ in ${𝒯}_{\mathrm{spqr}}^b$. We say a train loops at vertex $s$ for some split pair $\{s,t\}$, if there is a train whose train line contains the subsequence $⟨t,s,t⟩$. Intuitively, we traverse ${𝒯}_{\mathrm{spqr}}^b$ bottom-up, and mark nodes in ${𝒯}_{\mathrm{spqr}}^b$ (and the corresponding edge in their parent) as contractible or non-contractible and modify ${ℰ}_{\mu }$ using Reduction Rule 1. Due to the correspondence between vertices in a skeleton and vertices in $ℒ$ we use “vertex in a skeleton” and “vertex in $ℒ$” interchangeably. We do the following depending on the type of $\mu \ne {\mu }_r$.

Q-node:

We mark the edge corresponding to $\mu$ in the skeleton of the parent of $\mu$ as contractible (a contraction of the real edge corresponding to $\mu$ does not result in a different graph). If there is a train that loops at one of the poles of $\mu$, we mark this pole as terminal.

S-node:

Let $⟨c_1,\mathrm{\dots },c_{k-1}⟩$ be the path that corresponds to the skeleton of $\mu$ without the virtual edge of its parent. Every maximal subpath of contractible edges that does not contain any terminal $c_i$ is therefore a contractible transit component. Thus, we can apply Reduction Rule 1 on the graph that is induced by this subpath. If the entire path $⟨c_1,\mathrm{\dots },c_{k-1}⟩$ is contractible, then we mark the edge corresponding to $\mu$ in the skeleton of $\mu$’s parent as contractible, otherwise we mark it as non-contractible. In the contractible case, we check if there is a train that loops at the poles of $\mu$. If this is the case, we mark the corresponding pole(s) as terminal.

P-node:

Let $e_1,\mathrm{\dots },e_k$ be the edges between the poles of $\mu$ without the virtual edge corresponding to the parent of $\mu$. We consider every contractible edge among $e_1,\mathrm{\dots },e_k$ as a single transit component $C$ and apply Reduction Rule 1. Note that $C$ is a contractible transit component since the union of parallel contractible transit components is again a contractible transit component. If every edge $e_1,\mathrm{\dots },e_k$ is contractible, we mark the edge corresponding to $\mu$ in the skeleton of $\mu$’s parent as contractible. Further, we check if there is a train that loops at the poles of $\mu$. If this is the case, we mark the corresponding pole(s) as terminal.

R-node:

Let $C$ be the skeleton of $\mu$ without the virtual edge of its parent. If every edge in $C$ is contractible, then we test if $C$ is a contractible transit component with respect to the poles of $\mu$. If this is the case, we apply Reduction Rule 1 on $C$ and mark the edge corresponding to $\mu$ in the skeleton of $\mu$’s parent as contractible. Again, if there is a train that loops at one of the poles of $\mu$, we mark the corresponding pole(s) as terminal.

To process the root ${\mu }_r$ of ${𝒯}_{\mathrm{spqr}}^b$, we do the following depending on the type of the single child ${\mu }_c$ of ${\mu }_r$. If ${\mu }_c$ is an S-node, we check if the edge corresponding to ${\mu }_c$ is marked as contractible. If this is the case, we mark $b$ as contractible. Otherwise, we consider the maximal subpath of the skeleton of ${\mu }_c$ that now contains the edge corresponding to ${\mu }_r$ and apply Reduction Rule 1, if possible. If ${\mu }_c$ is a P- or R-node, we mark $b$ as contractible if ${\mu }_c$ is also contractible. To complete the processing of $b$, we finally check whether there is a train that loops at one of the poles of ${\mu }_r$, if this is the case we mark $b$ as non-contractible. Additionally, if this pole is also a cut vertex, we mark it as terminal. It remains to test for one special case. If for every skeleton in ${𝒯}_{\mathrm{spqr}}^b$ every edge is marked as contractible, except for a single edge $e^{\prime }$ in an R-node, test if $ℒ\setminus C_{e^{\prime }}$ is a contractible transit component where $C_{e^{\prime }}$ is the split component of $e^{\prime }$. If this is the case apply Reduction Rule 1.

After we have completed every block $b$ in $ℬ$, we mark every node $c$ in $𝒞$ as contractible if $c$ is not a terminal. Finally, we proceed similarly to the S-node previously. For every chain in ${𝒯}_{\mathrm{bc}}$ that contains only contractible vertices, we apply Reduction Rule 1.

A block-cut tree and an SPQR-tree can be computed in linear time each [12, 10]. It is easy to see that the total size of all skeletons is linear in the size of the location graph. Since each node is processed in time linear in the size of its skeleton and of the corresponding event graph, the entire algorithm takes time linear in the sizes of $ℒ$ and $ℰ$. $◀$

As a first improvement over $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E1" title="Equation 1 ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}$, we test a cutting plane approach. We start by solving a relaxation of $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E1" title="Equation 1 ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}$ that omits only the transitivity constraints (1c). To solve the separation problem, i.e., to find violated constraints (1c), we search for up to $k$ cycles in the auxiliary graph $G^{\prime }$ that contains a vertex for each location and has a directed edge $(p,q)$ if and only if $x_{pq}=1$. A cycle in $G^{\prime }$ then corresponds to a violated transitivity constraint. Note that for each pair of vertices $p\ne q$ in $G^{\prime }$, there is either an edge $(p,q)$ or an edge $(q,p)$, due to constraints (1b). Therefore, $G^{\prime }$ is a tournament graph. It is well known [14] that if there is a cycle in a tournament graph $G^{\prime }$, then there is also a cycle of length 3 in $G^{\prime }$. Thus, it suffices to search for cycles of length $3$.

We now propose a formulation that reduces the number of transitivity constraints by exploiting the structure of the location graph. In particular, given a tree decomposition $𝒯=(T,{\{X_t\}}_{t\in V(T)})$ of $ℒ$, we modify $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E1" title="Equation 1 ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}$ by using $U_t=\{(p,q,r):\{p,r\}\in {[X_t]}^2,q\in X_t,q\ne p,q\ne r\}$ instead of $U$. Thus, we obtain the following formulation ($\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$):

In other words, instead of introducing transitivity constraints for every triplet of locations in $U$, we restrict the transitivity constraints to triplets of locations that appear together in at least one bag. The intuition behind this formulation is the following. Consider a separation $(A,B)$ in $ℒ$ with a separator $A\cap B$. It is possible to find a turn-optimal ordering of $ℒ$ by separately finding turn-optimal orderings of $ℒ[A]$ and $ℒ[B]$ with the property that the ordering of $A\cap B$ is consistent in both orderings. In particular, programs for $ℒ[A]$ and $ℒ[B]$ need to share only constraints for vertices in $A\cap B$. Note that this intuition works only if we apply one separator to the location graph. For example, if we want to solve $ℒ[A]$ and $ℒ[B]$ recursively, we need to separate $ℒ$ throughout the recursion, as vertices can be part of multiple separators across different recursion steps. In this case, orderings of separators that are consistent for specific separations might be in conflict with each other. We show that a conflict between multiple separations cannot happen if we use a tree decomposition for the separation of $ℒ$.

First, observe that if the variables of type $x_{pq}$ indeed form a valid total ordering, then every possible turn is counted correctly by the variables $b_i$. Specifically, for every triplet $(p,q,r)\in R$, the variables $x_{pq}$ ($x_{qp}$) and $x_{qr}$ ($x_{rq}$) exist since every triplet in $R$ forms a path of length 2 in $ℒ$, and every edge in $ℒ$ is contained in at least one bag due to (T2). Thus, it remains to show that the variables of type $x_{pq}$ model a valid total ordering.

Consider the directed graph $G^{\prime }$ whose vertices correspond to the vertices in $ℒ$ and that has a directed edge $(p,q)$ if and only if $x_{pq}=1$. The underlying undirected graph of $G^{\prime }$ is a supergraph of $ℒ$, and the tree decomposition $𝒯$ of $ℒ$ is also a valid tree decomposition of $G^{\prime }$. Note that if $G^{\prime }$ is acyclic, then the variables of type $x_{pq}$ model a valid ordering. Towards a proof by contradiction, suppose that this is not the case and that $G^{\prime }$ does contain a cycle. Let $C$ be a shortest cycle in $G^{\prime }$. If $C$ has length 3, then $C$ is a clique and due to (P2), the tree $T$ has a node $t$ such that $C\subseteq X_t$. Due to constraints (1c), however, for every bag $X_i$ of $𝒯$, the graph $G^{\prime }[X_i]$ is acyclic. Hence, $C$ is a cycle of length at least 4.

We claim that every bag of $𝒯$ contains at most two vertices of $C$. Otherwise, there would be two vertices $u$ and $w$ of $C$ that are not consecutive along $C$ but, due to constraints (2f), the graph $G^{\prime }$ would contain the edge $(u,w)$ or the edge $(w,u)$. In the first case, the path from $w$ to $u$ along $C$ plus the edge $(u,w)$ would yield a directed cycle. In the second case, the path from $u$ to $w$ along $C$ plus the edge $(w,u)$ would also yield a directed cycle. In both cases, the resulting cycle would be shorter than $C$ (since $u$ and $w$ are not consecutive along $C$). This yields the desired contradiction and shows our claim.

Note that $𝒯$ restricted to $C$ is also a tree decomposition. However, since every bag contains at most two vertices of $C$, the restricted tree decomposition would have width 1, which is a contradiction since every tree decomposition of a cycle has width at least 2. Thus, the directed cycle $C$ does not exist, and $G^{\prime }$ is acyclic. $◀$ Note that this formulation requires only $𝒪(\mathrm{tw}{(ℒ)}^2\cdot |V(ℒ)|)$ variables and $𝒪(\mathrm{tw}{(ℒ)}^3\cdot |V(ℒ)|)$ many constraints. This is a significant improvement over $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E1" title="Equation 1 ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">1</span></a>}$ if $\mathrm{tw}(ℒ)$ is small, which can be expected since train infrastructure is usually sparse and “tree-like”.

Our implementation of Reduction Rule 1 is restricted to exhaustively contract chains. But even with this restriction, the reduction rule proves to be effective on the provided dataset. On average, the number of locations was reduced by 75%, where the best result was a reduction by 89% (instance 50-4) and the worst result was a reduction by 55% (instance 20-3). A full evaluation is shown in Figure 7.

Each formulation was implemented with only one variable for each unordered pair of locations and without constraints (1b). Instead, if we created variable $x_{pq}$ for the unordered pair $\{p,q\}$ and $x_{qp}$ was needed in the formulation, we substituted $1-x_{pq}$ for $x_{qp}$. Since the computation of an optimal tree decomposition is $\mathrm{𝖭𝖯}$-hard, we used the Min-Degree Heuristic implemented in Networkx to compute a tree decomposition for $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$. The additional time needed for computing this tree decomposition was counted towards the runtime of $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$. We tested the cutting plane method and $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$ on the original instances which we call initial instances and the instances that were reduced by our implementation of Reduction Rule 1 which we call reduced instances. We imposed a time limit of one hour on every experiment. The result of each experiment is the average value over 5 repetitions of the experiment. The cutting plane approach on the initial instances was able to solve 11 out of 19 instances. An instance was either always solved to optimality or never solved to optimality across all repetitions of the experiment. The largest instance that was solved to optimality contained 465 locations (and 19 trains) and was solved in 3509 s. The smallest instance that was not solved within the time limit contained 277 locations (and 8 trains). In contrast, the cutting plane approach was able to solve every reduced instance within 70 s. Applied to the reduced instances, the cutting plane approach was 625 times faster than when applied to the initial instances (averaged over those that were solved within the time limit). See Figure 8 for more details on the performance of the cutting plane approach.

$\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$ solved every instance (initial or reduced) in less than a second (see Figure 8 for details). Still, the reduction helped, making $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$ on average 3.98 times faster than on the initial instances. On the reduced instances, $\mathrm{𝖨𝖫𝖯}\text{<a href="\#S5.E2" title="Equation 2 ‣ An integer linear program via tree decompositions. ‣ 5 Exact Integer Linear Programming Approaches ‣ Visualization of Event Graphs for Train Schedules" class="ltx\_ref ltx\_font\_sansserif"><span class="ltx\_text ltx\_ref\_tag">2</span></a>}$ was on average 103 times faster than the cutting plane approach on the reduced instances (and 22,845 times faster than the cutting plane approach on the initial instances).