%\documentclass{llncs}
\documentclass[11pt,onecolumn,oneside]{article}
\usepackage{llncsdoc}
\usepackage{amsfonts,stmaryrd}
\usepackage{wasysym}
\usepackage{dsfont}
\usepackage{float}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{fancyvrb}
\usepackage{wrapfig}
\usepackage{soul} %Strike through text package
\usepackage[export]{adjustbox} %figure left align
\usepackage{graphicx,subfigure}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{condition}[thm]{Condition}
\newtheorem{proof}[thm]{Proof}

%\setlength{\intextsep}{10pt plus 2pt minus 2pt}
\setlength{\evensidemargin}{0.05in}
\setlength{\oddsidemargin}{0.05in}
\setlength{\marginparwidth}{0.6in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.3in}
\addtolength{\parskip}{0.0 cm}

\setlength{\topmargin}{0.25in}

\begin{document}

\centerline{\LARGE\bf Appendix}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proofs of Propositions and Lemmae} \label{app:proofs}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{proof}[of Prop. \ref{prop:premax}]%\\
\underline{Equivalence:} We define a {\em backward path} from $b$ to $a$ as a path that consists only of  backward 0-edges that leads from $b$ to $a$; denote such a path by $BP(b,a)$. We define a full order $\apprle$ on the events of the pattern, so that $a \apprle b$ iff $a$ appears chronologically before $b$. For simplicity, we break the updating of $G$ to $n$ single update steps with a single update step at a time. We show that $G \equiv G_0 \equiv G_1 \equiv ... \equiv G_n=G'$, where these graphs are the intermediate graphs along the $n$ update steps. We examine the update step of $G_i$.

If an edge $e=(u,v,w)$ is removed from $G_i$, then obviously $G_i \ll G_{i+1}$. Let $P$ be the shortest $(u,v)$-$path$. We define $b_0=u, a_k=v$. The general form of this path is $(BP(b_0,a_0), (a_0, b_1),$ $BP(b_1,a_1), (a_1, b_2), \dots , (a_{k-1},b_k), BP(b_k,a_k))$.
There is an edge $(a_i,b_{i+1})$ (either simple or overpassing) for each $0 \leq i \leq k-1$. For each $1<i<k$ it must hold that $a_{i-1} \apprle a_i$, else we can remove the sub-path $(a_{i-1}, b_i, BP(b_i,a_{i-1}))$ from $P$ and get a shorter $(u,v)$-$path$, a contradiction. For each $0<i<k-1$ it must hold that $b_i \apprle b_{i+1}$, else we can remove the sub-path $(BP(b_{i+1},a_i), a_i, b_{i+1})$ from $P$ and get a shorter $(u,v)$-$path$, a contradiction. Also, either $a_i \apprle b_i$ or $a_i=b_i$. We note that a simple path $P$ from $u$ to $v$ is a special case of this form. Also, $w(P)=\sum w(a_i,b_{i+1}) < w(e)$. Let $H$ be a history that fits $G_{(i+1)}$. Then $H(u,v) \leqslant H(a_0,b_k) = H(a_0,b_1) + \sum H(b_i,b_{i+1}) \leqslant \sum H(a_i,b_{i+1}) \leqslant \sum w(a_i,b_{i+1}) = w(P) < w(e)$. Since the removal of $e$ is the only change in the graph, $H$ must also fit $G_i$. We get that $G_{i+1} \ll G_i$, and therefore $G_i \equiv G_{i+1}$.

If the weight of a simple edge $e=(u,v,w)$ in $G_i$ is reduced to $w'$ in $G_{(i+1)}$, then there is an edge $e'=(u',v')$ with weight $w'$ that overpasses $e$, and clearly $G_{(i+1)} \ll G_i$. Let $P$ be the shortest $(u,v)$-$path$. This path necessarily takes the following form: $P=(BP(u,u'),(u',v'),BP(v',v))$. It may hold that $u'=u$ or $v'=v$ (but not both). Let $H$ be a history that fits $G_i$. Then $H(u,v) \leqslant H(u',v') \leqslant w'$. Since the reduced weight of $e$ is the only change in the graph, $H$ must also fit $G_{i+1}$. We get that $G_i \ll G_{i+1}$, and therefore $G_i \equiv G_{i+1}$. We thus showed that for every $1 < i < n-1$, $G_i \equiv G_{(i+1)}$, and hence $G \equiv G'$.

\noindent
\underline{Minimality:} Assume toward a contradiction that we can remove an overpassing edge $e=(a,b)$ from $G'$ or reduce the weight of a simple edge $e=(a,b)$ in $G'$, such that the resulting graph $G''$ is equivalent to $G'$.

Assume $e$ is a simple edge whose weight is reduced from $w'$ in $G'$ to $w''$ in $G''$.
$G'$ is the graph generated by the preprocessing process, so we know that $e$ is the shortest $(a,b)$-$path$ in G'.
Let $H$ be a history that fits $G'$ and uses the full weight of $e$ in $G'$, namely the time elapsed between the events $a$ and $b$ is $w'$.
We are assured such a history exists because $e$ is the shortest $(a,b)$-$path$ in $G'$. the time elapsed between events $a$ and $b$ cannot violate any overpassing edge $e^*$ since it must weigh at least as much as $e$, and we can assign all other simple edges $0$ time lapses in $H$.
$H$ clearly does not fit $G''$ since it violates the constraint on $e$ in $G''$.
This is contradictory to the equivalence of $G'$ and $G''$.

Assume $e$ is an overpassing edge that is removed.
$G'$ is the graph generated in the preprocessing phase, so we know that $e$ is the shortest $(a,b)$-$path$.
Next we show that there is a history $H'$ that fits $G'$ (and therefore $G''$) such that $H(a,b)=w(e)$, and that $H'$ can be augmented by adding $1$ to $H'(a,b)$ resulting in a new history $H''$, so that $H''$ fits $G''$, but not $G'$.
Let $(e_1,e_2,...,e_k)$ be the simple $(a,b)$-$path$.
We describe a recursive method of constructing $H'$.
At first $H'(a_i,a_{i+1})=0$ for all $1 \leq i \leq n-1$.
In particular $H'(e_i)=0$ for all $1 \leq i \leq k-1$.
Obviously $H'$ fits $G'$.
Let $H'(e_i)=x_i$ for all $1 \leq i \leq k-1$ at some step of the recursive method.
We show that while $\sum_1^k x_i < w(e)$, we can add $1$ to some $x_i$ and remain with a history that fits $G'$.
We say $e_i$ is {\it full} if $x_i=w(e_i)$. The edges $e_1,...,e_k$ cannot be all full, because then the $(a,b)$-$path$ $(e_1,...,e_k)$ is shorter than $e$, which is a contradiction.
Now, there has to be some $x_i$ that can be augmented to $x_i+1$ so that we remain with a history that fits $G'$.
Explanation: Assume to the contrary that such $x_i$ does not exist.
Then every $e_j$ that is not full is overpassed by an edge $e_j'$ such that $w(e_j')=x_j$.
In this case, we can construct an $(a,b)$-$path$ $P$ as follows:
We advance from $a$ towards $b$ using full edges.
When we arrive at an edge $e_j$ that is not full, we may travel back with 0-edges to the source of $e_j'$, add $e_j'$ to $P$ thus overpassing $e_j$, and continue advancing by the same rules until we reach $b$.
Clearly $w(P) = \sum_1^k x_i < w(e)$, which is a contradiction. Hence there exists the desired $e_i$ that is not full, where $x_i$ can be augmented to $x_i+1$ so that we remain with a history that fits $G'$.

This recursive method is finite, for at some point we shall have values $x_1,...,x_k$ such that $H'(a,b) = \sum_1^k x_i = w(e)$ and $H'$ fits $G'$.
There has to be some $e_i$ that is not full in $H'$ because $e$ is the unique shortest $(a,b)$-$path$ (for any other $(a,b)$-$path$ $P$, $w(P) > w(e)$).
By the same explanation as above, there has to be some $e_i$ such that $x_i$ can be augmented to $x_i+1$ so that we remain with a history that fits $G''$, since otherwise we get an $(a,b)$-$path$ $P$ in $G''$, with $w(P)=w(e)$.
We denote the history following this augmentation $H''$.
$H''$ fits $G''$ but does not fit $G'$, and therefore $G' \not\equiv G''$, which is a contradiction.
\end{proof}

\begin{proof} [of Prop. \ref{prop:premaxmin}]
\underline{Equivalence:} First, it is easy to observe that $TP' \ll TP$: Let $H$ be a pattern history. For any two pattern events $a,b$ such that $a \apprle b$, there is a simple $(a,b)$-$path$ $P$ of simple edges in $G$, and the weight of the shortest $(a,b)$-$path$ $P'$ must be at most $w(P)$. We get: $H$ fits $TP' \Rightarrow H(a,b) \leq w(P') \Rightarrow H(a,b) \leq w(P)$. Similarly, there is a simple backward $(b,a)$-$path$ $Q$ of simple backward edges in $G$, and the weight of the shortest $(b,a)$-$path$ $Q'$ must be at most $w(Q)$. We get: $H$ fits $TP' \Rightarrow H(a,b) \geq -w(Q') \Rightarrow H(a,b) \geq -w(Q)$. This holds for all pairs of events $a,b$ such that $a \apprle b$, hence $TP' \ll TP$.
If $P$ is a path between two events in $G$, we define $L(P)$ as the number of edges in $P$.

We prove by induction that $TP \ll TP'$. The induction statement is as follows:
For any $k \in \mathbb{N}$
, for any pair of pattern events $a,b$ such that $a \apprle b$, the following hold:
(a) If $P$ is an $(a,b)$-$path$ with $L(P)=k$ in $G$, then in any history $H$ that fits $TP$, $H(a,b) \leq w(P)$ holds.
(b) If $Q$ is a $(b,a)$-$path$ $L(Q)=k$ in $G$, then in any history $H$ that fits $TP$, $H(a,b) \geq -w(Q)$ holds.

If (a) and (b) hold and $H$ is some history that fits $TP$, then it also fits $TP'$ because its constraints are defined by the weights of paths in $G$.

\noindent
{\bf Basis.} If $P$ is an $(a,b)$-$path$ with weight $w$ and with $L(P)=1$ in $G$, then $P$ is a single edge between the events $a,b$, i.e. it represents a max constraint $w$. If $H$ is a history that fits $TP$ then $H(a,b) \leq w$, and thus (a) holds.

Similarly, if $Q$ is a $(b,a)$-$path$ with weight $w$ and with $L(Q)=1$, then $Q$ is a single backward edge between the events $b,a$, i.e. it represents a min constraint $-w$. If $H$ is a history that fits $TP$ then $H(a,b) \geq -w$, and thus (b) holds.

\noindent
{\bf Inductive Step.} We assume the inductive hypothesis, namely that the induction step is true for some $k \in \mathbb{N}$
, and prove that it is then also true for $k+1$. Let $H$ be some history that fits $TP$:\\
(a) Let $P$ be an $(a,b)$-$path$ in $G$ with $L(P)=k+1$, and let $H$ be some history that fits $TP$. Let $P_0$ be the $k$-prefix of $P$, i.e. $P=(P_0,(a',b,w))$ for some $(a',b,w) \in G$. We consider three distinct cases:\\
$\bullet$ $a' \apprle a$: Here $(a',b,w) \in CMax$. By the inductive hypothesis part (b), $H(a',a) \geq -w(P_0)$. Also, due to the edge $(a',b,w)$, $H(a',b) \leq w$ holds. Hence $H(a,b) \leq w - (-w(P_0)) = w + w(P_0) = w(P)$.\\
$\bullet$ $a \apprle a' \apprle b$: Here too $(a',b,w) \in CMax$. By the inductive hypothesis part (a), $H(a,a') \leq w(P_0)$. Also, due to the edge $(a',b,w)$, $H(a',b) \leq w$ holds. Hence $H(a,b) \leq w + w(P_0) = w(P)$.\\
$\bullet$ $b \apprle a'$: Here $(b,a',-w) \in CMin$. By the inductive hypothesis part (a), $H(a,a') \leq w(P_0)$. Also, due to the edge $(b,a',w)$, $H(b,a') \geq -w$ holds. Hence $H(a,b) \leq w(P_0) -(-w) = w(P_0) + w = w(P)$.\\
(b) Let $Q$ be a $(b,a)$-$path$ in $G$ with $L(Q)=k+1$, and let $H$ be some history that fits $TP$. Let $Q_0$ be the $k$-prefix of $Q$, i.e. $Q=(Q_0,(b',a,w))$ for some $(b',a,w) \in G$. We consider three distinct cases:\\
$\bullet$ $b \apprle b'$: Here $(a,b',-w) \in CMin$. By the inductive hypothesis part (a), $H(b,b') \leq w(Q_0)$. Also, due to the edge $(b',a,w)$, $H(a,b') \geq -w$ holds. Hence $H(a,b) \geq -w - w(Q_0) = -(w + w(Q_0)) = -w(Q)$.\\
$\bullet$ $a \apprle b' \apprle b$: Here too $(a,b',-w) \in CMin$. By the inductive hypothesis part (b), $H(b',b) \geq -w(Q_0)$. Also, due to the edge $(b',a,w)$, $H(a,b') \geq -w$ holds. Hence $H(a,b) \geq -w - w(Q_0) = -w(Q)$.\\
$\bullet$ $b' \apprle a$: Here $(b',a,w) \in CMax$. By the inductive hypothesis part (b), $H(b',b) \geq -w(Q_0)$. Also, due to the edge $(b',a,w)$, $H(b',a) \leq w$ holds. Hence $H(a,b) \geq -w(Q_0) -w = -w(Q)$.

\noindent
\underline{No-Negative:} Assume there is a history $H$ that fits $TP$.
Now, if there is a negative cycle $C$ in $G$, let $a,b$ be events in $C$ such that $a \apprle b$.
Then we may describe $C$ as the concatenation of two paths, $C=(P_{a,b},P_{b,a})$, where $P_{a,b}$ is an $(a,b)$-$path$ and $P_{b,a}$ is a $(b,a)$-$path$.
From (1) we know that $H(a,b) \leq w(P_{a,b})$ and $H(a,b) \geq -w(P_{b,a})$ hold.
But $0 > w(C) = w(P_{a,b}) + w(P_{b,a})$, and hence $H(a,b) \geq -w(P_{b,a}) > w(P_{a,b}) \geq H(a,b)$, a contradiction.
Therefore there is no negative cycle in $G$.

Now assume there is no negative cycle in $G$.
We prove inductively that there exists a history that fits $TP$.
We define the $k$-prefix of $TP$, denoted as $TP_k$, as the temporal pattern defined by the events $a_1,...,a_k$ and by the time windows $\{tw \mid tw \in TP \wedge ((dst(tw) \apprle a_k) \vee (dst(tw)=a_k))\}$.
The induction statement is as follows: For any $k \in \mathbb{N}, 2 \leq k \leq n$, there exists a history that fits $TP_k$.\newline
{\bf Basis.} $k=2$.
$\underline{tw}(a_1,a_2) \leq \overline{tw}(a_1,a_2)$, else there is an $(a_1,a_2)$-$path$ and an $(a_2,a_1)$-$path$ such that their sum is negative, i.e. a negative cycle, in contradiction to our assumption.
A history $((a_1,0) , (a_2,\overline{tw}(a_1,a_2)))$ clearly fits $TP_2$.\newline
{\bf Inductive Step.} We assume the inductive hypothesis, namely that the induction step is true for some $k \in \mathbb{N}, 2 \leq k \leq n-1$, and prove that it is then also true for $k+1$.
Let $H$ be a history that fits $TP_k$.
Let $dl=min_{i=3}^k\{H(a_i)+ \overline{tw}(a_i,a_{k+1})\}$.
$dl$ is the deadline for reaching $a_{k+1}$.
Let $ll=max_{i=3}^k\{H(a_i)+ \underline{tw}(a_i,a_{k+1})\}$.
$ll$ is the liveline for reaching $a_{k+1}$, i.e. $a_{k+1}$ must not happen before time $ll$.
For any $1 \leq r \leq k$ it holds that $\underline{tw}(a_r,a_{k+1}) \leq ll$ and $dl \leq \overline{tw}(a_r,a_{k+1})$.
Therefore, if $ll \leq dl$, we expand $H$ by defining $H(a_{k+1})$ such that $ll \leq H(a_{k+1}) \leq dl$, and $H$ will fit $TP_{k+1}$.

We assume toward a contradiction that $dl < ll$.
Let $a_i$ be an event such that $H(a_i)+ \underline{tw}(a_i,a_{k+1})=ll$, and
let $a_j$ be an event such that $H(a_j)+ \overline{tw}(a_j,a_{k+1})=dl$.
Let $P_{k+1,i}$ and $P_{j,k+1}$ be paths in $G$ with weights $-\underline{tw}(a_i,a_{k+1})$ and $\overline{tw}(a_j,$ $a_{k+1})$, respectively.
We consider two cases.\\
$\bullet$ $(a_j \apprle a_i) \vee (a_j=a_i)$: Let $P_{i,j}$ be the simple backward $(a_i,a_j)$-$path$ (empty if $a_j=a_i$). $w(P_{i,j}) \leq 0$. We get a cycle $C=(P_{j,k+1},P_{k+1,i},P_{i,j})$. $w(C) = w(P_{j,k+1}) + w(P_{k+1,i}) + w(P_{i,j}) \leq w(P_{j,k+1}) + w(P_{k+1,i}) = dl - ll < 0$.
C is a negative cycle, in contradiction to the assumption that there are no negative cycles in $G$.\\
$\bullet$ $a_i \apprle a_j$: The path $(P_{j,k+1},P_{k+1,i})$ has weight $\overline{tw}(a_j,a_{k+1}) - \underline{tw}(a_i,a_{k+1})$, hence $-\underline{tw}(a_i,a_j) \leq \overline{tw}(a_j,a_{k+1}) - \underline{tw}(a_i,a_{k+1})$, and therefore $\underline{tw}(a_i,a_{k+1}) - \overline{tw}(a_j,$ $a_{k+1}) \leq \underline{tw}(a_i,a_j)$.
Now $H(a_j) - H(a_i) = (dl - \overline{tw}(a_j,a_{k+1})) - (ll - \underline{tw}(a_i,a_{k+1}))$ $= (dl - ll) + (\underline{tw}(a_i,a_{k+1}) - \overline{tw}(a_j,a_{k+1})) < \underline{tw}(a_i,a_{k+1}) - \overline{tw}(a_j,$ $a_{k+1}) \leq \underline{tw}(a_i,a_j)$. This is contradictory to the assumption that $H$ fits $TP_k$.

\noindent
\underline{Minimality:} Let $tw(a,b)$ be a time window in $TP'$. We show that any contraction from above or from below, i.e. decreasing $\overline{tw}(a,b)$ or increasing $\underline{tw}(a,b)$ respectively, will result in a temporal pattern $TP''$ that is not equivalent to $TP'$.
Let $H$ be some history that fits $TP'$. If there are $k-1$ events between $a$ and $b$, let $tw_1,tw_2,...,tw_k$ be the simple time windows between $a$ and $b$. 
Let the source and destination of $tw_i$ be $b_i$ and $b_{i+1}$ respectively, $1 \leq i \leq k$. Specifically $a=b_1$ and $b=b_{k+1}$.

Assume $\overline{tw}(a,b)$ is decreased.
We describe a recursive method of augmenting $H$.
Let $H(tw_i)=x_i$ for all $1 \leq i \leq k$ at some step of the recursive method.
We show that while $\sum_1^k x_i < \overline{tw}(a,b)$, we can add $1$ to some $x_i$ and remain with a history that fits $TP'$.
We say $tw_i$ is {\it full} if $x_i=\overline{tw_i}$.
$tw_1,...,tw_k$ cannot be all full, because then the weight of the $(a,b)$-$path$ $(P_1,...,P_k)$ in $TP$, where $P_i$ is the shortest $(b_i,b_{i+1})$-$path$ in $TP$, is smaller than $\overline{tw}(a,b)$, which is a contradiction to the definition of $tw$.
Now, there has to be some $x_i$ that can be augmented to $x_i+1$ so that we remain with a history that fits $TP'$.

Explanation: Assume to the contrary that such $x_i$ does not exist.
Then every $tw_j$ that is not full is subsumed by a time window $tw_j'$ such that $\overline{tw_j'}=x_j$, i.e. there is a path $P_j'$ between the source and destination of ${tw_j'}$, with $w(P_j')=x_j$.
In this case, we can construct an $(a,b)$-$path$ $P$ as follows:
We advance from $a$ towards $b$ using full time windows.
When we arrive at a time window $tw_j$ that is not full, we may travel back with non-positive edges to the source of $tw_j'$, add $P_j'$ to $P$ thus overpassing $b_{j+1}$, and continue advancing by the same rules until we reach $b$.
Clearly $w(P) \leq \sum_1^k x_i < \overline{tw}(a,b)$, which is a contradiction to the definition of $tw$.

Hence there exists the desired $tw_i$ that is not full, where $x_i$ can be augmented to $x_i+1$ so that we remain with a history that fits $TP'$. This procedure is finite, for at some point we shall have values $x_1,...,x_k$ such that $H(a,b) = \sum_1^k x_i = \overline{tw}(a,b)$ and $H$ fits $TP'$.
Let $TP''$ be the temporal pattern after decreasing $\overline{tw}(a,b)$. Clearly $H$ does not fit $TP''$, hence $TP' \not\equiv TP''$.

The proof of the case where $\underline{tw}(a,b)$ is increased is similar to (a).
\end{proof}

\begin{proof}[of Lemma \ref{lem:linearrecalc}]
Assume without loss of generality that $TP=TP^*$.
We define a {\it forward} ({\it backward}) edge as any edge $(a_i,a_k)$ such that $a_i \apprle a_k$ ($a_k \apprle a_i$).
We denote the weight of an edge $(a,b)$ in a graph $G$ as $w|_G(a,b)$.
We use $\circ$ to denote concatenation of graph paths: $(e_1, \dots, e_k) \circ (e'_1, \dots, e'_l) = (e_1, \dots, e_k, e'_1, \dots e'_l)$, where $e_i, e'_j$ are graph edges, $1 \leq i \leq k, 1 \leq j \leq l$.\\
$\bullet$
Let $P$ be an $(a_r,a_{r+1})$-$path$ of minimal weight in $G(TP|_H)$.
Let $P_0=((a_r,a_{r-1})$ $,(a_{r-1},$ $a_{r-2}), \dots,(a_{j+1},a_j))$ be the maximal prefix of $P$ containing only backward edges.
Without loss of generality, every edge in $P_0$ is a simple backward edge: If some edge $(a_{r-i},a_{r-k})$ in $P_0$, $a_{r-k} \apprle a_{r-i}$, is an overpassing backward edge then because $H$ is a fitting history we have:
$\sum_{l=i}^{k-1} w|_{G(TP|_H)}(a_{r-l},a_{r-(l+1)})$ $= \sum_{l=i}^{k-1} -H(a_{r-(l+1)},a_{r-l}) = -H(a_{r-k},a_{r-i}) \leq w|_{G(TP)}(a_{r-i},a_{r-k}) =w$ $|_{G(TP|_H)}(a_{r-i},a_{r-k})$, and we can therefore substitute $(a_{r-i},a_{r-k})$ in $P$ with $((a_{r-l},a_{r-(l+1)}))_{l=i}^{k-1}$.

Let $(a_j,a_k)$ be the first forward edge in $P$, i.e. the first edge succeeding $P_0$.
If $a_k \apprle a_r$, then $\sum_{l=k}^{j+1} w|_{G(TP|_H)}(a_l,a_{l-1})$ $+$ $w|_{G(TP|_H)}(a_j,a_k) = \sum_{l=k}^{j+1} -H(a_l,$ $a_{l-1})$ $+$ $w|_{G(TP|_H)}(a_j,a_k)$ $= -H(a_j,a_k) + w|_{G(TP|_H)}(a_j,a_k) = -H(a_j,a_k) + w|_{G(TP)}(a_j,a_k) \geq -H(a_j,a_k) + H(a_j,a_k)$ $= 0$.
We can therefore remove the sub-path $((a_l,a_{l-1}))_{l=k}^{j+1} \circ (a_j,a_k)$ from $P$.

If $a_{r+1} \apprle a_k$, we examine two distinct cases:
If there is no edge in $P$ in the suffix $P - P_0$ whose destination is $a_s$, $a_s \apprle a_r$, then this suffix only contains edges that are retained from $G(TP)$.
Since $(a_j,a_{r+1})$ is the shortest $(a_j,a_{r+1})$-$path$ in $G(TP)$, we have $w|_{G(TP|_H)}(a_j,a_{r+1}) = w|_{G(TP)}(a_j,a_{r+1}) \leq w|_{G(TP)}(a_j,a_k) + w|_{G(TP)}(a_k,a_{r+1}) = w|_{G(TP|_H)}(a_j,a_k) + w|_{G(TP|_H)}(a_k,a_{r+1})$, and hence we can substitute the suffix of $P$ starting at the edge $(a_j,a_k)$ with $(a_j,a_{r+1})$.
If there is an edge in $P$ in the suffix $P - P_0$ whose destination is $a_d$, $a_d \apprle a_r$, then let $P_1$ be the prefix of $P - P_0$ ending with this edge.
$P_1$ contains only edges that are retained from $G(TP)$.
Similarly to the above consideration, since $(a_j,a_d)$ is the shortest $(a_j,a_d)$-$path$ in $G(TP)$, we have $w|_{G(TP|_H)}(a_j,a_d) = w|_{G(TP)}(a_j,a_d) \leq w|_{G(TP)}(P_1) = w|_{G(TP|_H)}(P_1)$, and hence we can substitute $P_1$ with $(a_j,a_d)$.
Thus we revert to the case where $(a_j,a_k) \apprle a_r$.

We may therefore say without loss of generality that the first (and only) forward edge $(a_j,a_k)$ in $P$ is such that $a_k = a_{r+1}$.\\
$\bullet$
Let $P$ be an $(a_{r+1},a_r)$-$path$ of minimal weight in $G(TP|_H)$.
Without loss of generality, the first edge in $P$ is $(a_{r+1},a_j)$ for some $1 \leq j \leq r$, $a_j \apprle a_r$: Let $P_0$
%=((a_{r+1},a_{i_1}),(a_{i_1},a_{i_2}), \dots, (a_{i_{k-1}},a_{i_k}))$
be the maximal prefix of $P$ that contains no edge whose destination is $a_d$, $a_d \apprle a_r$.
%such that $\forall$ $1 \leq l \leq k,$ $a_{r+1} \apprle a_{i_l}$.
Let $(a_i,a_d)$ be the next edge in $P$ succeeding $P_0$, $(a_d \apprle a_r)$. 
If $a_d = a_r$, we get the desired property.
Otherwise $P_0$ only contains edges that are retained from $G(TP)$.
Since $(a_{r+1},a_d)$ is the shortest $(a_{r+1},a_d)$-$path$ in $G(TP)$, we have $w|_{G(TP|_H)}(a_{r+1},a_d) = w|_{G(TP)}(a_{r+1},a_d) \leq w|_{G(TP)}(P_0) + w|_{G(TP)}(a_i,a_d) = w|_{G(TP|_H)}(P_0) + w|_{G(TP|_H)}(a_i,a_d)$.
We can therefore substitute $P_0 \circ (a_i,a_d)$ in $P$ with $(a_{r+1},a_d)$.
 
Let $P_s$ be the maximal suffix of $P$ containing only forward edges. Without loss of generality every edge in $P_s$ is a simple forward edge: If some edge $(a_{r-i},a_{r-k})$ in $P_s$, $a_{r-i} \apprle a_{r-k}$ is an overpassing forward edge, then because $H$ is a fitting history we have $\sum_{l=r-i}^{r-k-1} w|_{G(TP|_H)}(a_l,a_{l+1}) = \sum_{l=r-i}^{r-k-1} H(a_l,a_{l+1}) = H(a_{r-i},a_{r-k}) \leq w|_{G(TP)}(a_{r-i},a_{r-k}) = w|_{G(TP|_H)}(a_{r-i},a_{r-k})$.
We can therefore substitute $(a_{r-i},a_{r-k})$ in $P$ with $((a_l,a_{l+1}))_{l=r-i}^{r-k-1}$.
Also, the destination of a forward edge in $P_s$ cannot be some $a_d$, $a_r \apprle a_d$ $\wedge$ $a_r \neq a_d$, since the suffix ends in $a_r$.

Let $(a_k,a_q)$ be the backward edge preceding $P_s$ in $P$.
If $a_k = a_{q+1}$ then we can remove the 0-weight sub-path $((a_k,a_q),(a_q,a_k))$ from $P$.
Otherwise, if $a_k \apprle a_r$, then $(a_q,a_k)$ is an overpassing forward edge retained from $G(TP)$, and we have $\sum_{l=k}^{q+1} w|_{G(TP|_H)}(a_l,a_{l-1})$ $+$ $w|_{G(TP|_H)}(a_q,a_k) = \sum_{l=k}^{q+1} -H(a_l,a_{l-1})$ $+$ $w|_{G(TP|_H)}(a_q,a_k) = -H(a_q,a_k)$ $+$ $w|_{G(TP|_H)}(a_q,$ $a_k) = -H(a_q,a_k)$ $+$ $w|_{G(TP)}$ $(a_q,a_k) \geq -H(a_q,a_k) + H(a_q,a_k) = 0$.
We can therefore remove the sub-path $((a_l,a_{l-1}))_{l=k}^{q+1} \circ (a_q,a_k)$ from $P$.

The remaining case is when $a_{r+1} \apprle a_k$.
Let $P_0$ be the maximal suffix of $P - ((a_k,a_q) \circ P_s)$ that only contains edges retained from $G(TP)$.
Then the edge $e$ preceding $P_0$ is either $(a_{q-1},a_q)$ or $(a_{q+1},a_q)$.
If $e = (a_{q-1},a_q)$ then we get a contradiction to the maximality of $P_s$.
If $e = (a_{q+1},a_q)$ then, as before, we can remove the 0-weight sub-path $((a_k,a_q),(a_q,a_k))$ from $P$. Hence, we may assume without loss of generality that $P = P_0 \circ ((a_k,a_q) \circ P_s$, that $P_0$ contains only edges retained from $G(TP)$, and that $a_q = a_j$. We get that $P_0 \circ (a_k,a_q) = ((a_{r+1},a_j) \circ P'_0)$ where $P_0'$ ends in $a_j$. Therefore, $P_0'$ can be removed from $P$ so that we remain with the path $(a_{r+1},a_j) \circ P_s$ as required.
\end{proof}

\end{document} 
