# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 4 Canonical Estimate
: _Let \(G\) be an FJ-DAG shown in Figure 4, and let \(F\) be a canonical estimate for \(G\) with length \(h\). Then, for each \(i=1,\cdots,m\), \(\hat{w}(e_{i}^{t})\) and \(\hat{w}(e_{i}^{b})\) are unique up to their exchange._  
Proof. : We first consider the case that \(\mathit{level}(G_{i})=0\). Then, \(\hat{w}(e_{i}^{t})+\hat{w}(e_{i}^{b})=h\) holds. If both \(e_{i}^{t}\) and \(e_{i}^{b}\) are saturated, then the value assignment is unique. If both \(e_{i}^{t}\) and \(e_{i}^{b}\) are unsaturated, then by C2, \(|\hat{w}(e_{i}^{t})-\hat{w}(e_{i}^{b})|\leq 1\) holds and the value assignment to these edges are unique up to exchange of them. Suppose that \(e_{i}^{t}\) is saturated and \(e_{i}^{b}\) is unsaturated. Then, by C2, \(\hat{w}(e_{i}^{t})\leq\hat{w}(e_{i}^{b})+1\) holds. If \(\hat{w}(e_{i}^{t})<\hat{w}(e_{i}^{b})+1\), then this is the unique assignment to these two edges. If \(\hat{w}(e_{i}^{t})=\hat{w}(e_{i}^{b})+1\), then we can obtain another assignment by decrementing \(\hat{w}(e_{i}^{b})\) by one and incrementing \(\hat{w}(e_{i}^{b})\) by one. No other assignments are possible. Therefore, the value assignment is unique up to their exchange. This also holds for the case that \(e_{i}^{t}\) is unsaturated and \(e_{i}^{b}\) is saturated. Next, we consider the case that \(\mathit{level}(G_{i})>0\). Suppose that \(G_{i}\) has no unsaturated cut. Then, \(G_{i}\) has a goal path with saturated edges only. Let \(h_{i}\) be the length of such a saturated goal path. Note that \(h_{i}\) is uniquely determined, and all goal paths of \(G_{i}\) have the same estimated length since \(F\) is homogeneous. Therefore, \(\hat{w}(e_{i}^{t})+\hat{w}(e_{i}^{b})=h-h_{i}\) is also unique. By the same argument as in the case \(\mathit{level}(G_{i})=0\), we can prove the lemma. Suppose that \(G_{i}\) has at least one unsaturated cut. Let \(e_{(s)}^{x}\) (\(x\) is \(t\) or \(b\)) be an unsaturated edge in \(G_{i}\) such that it is on a minimum unsaturated cut \(C\) of \(G_{i}\) and \(\hat{w}(e_{(s)}^{x})=\hat{w}(G_{i})^{\downarrow}\). Let \(G_{(s)}\) be the sub FJ-DAG having \(e_{(s)}^{x}\) as the top or bottom edge. By C3, every edge in \(G_{(s)}\) is with an estimated length no greater than \(\hat{w}(e_{(s)}^{x})\). We claim that \(G_{(s)}\) has a goal path such that all unsaturated edges on the path are with estimated length \(\hat{w}(e_{(s)}^{x})\). Assume that \(G_{(s)}\) has no such goal paths. Then, \(G_{(s)}\) has an unsaturated cut \(C^{\prime}\) with a characteristic vector smaller than that of \(\{e_{(s)}^{x}\}\). By replacing \(e_{(s)}^{x}\) with \(C^{\prime}\) in the cut \(C\), we obtain an unsaturated cut of \(G_{i}\) with a smaller characteristic vector than \(C\), which is a contradiction. Since \(G_{(s)}\) is homogeneous, any goal path in \(G_{(s)}\) has the same estimated length, and it is uniquely determined. Let \(\pi\) be a goal path that goes through \(e_{(s)}^{x}\). \(\pi\) has the form  
\[e_{(1)}^{t}\cdots e_{(s)}^{t}\cdots e_{(r)}^{t}e_{(r)}^{b}\cdots e_{(s)}^{b} \cdots e_{(1)}^{b}\]  
where \(e_{(1)}^{t}=e_{i}^{t}\) and \(e_{(1)}^{b}=e_{i}^{b}\). Note that subpaths \(e_{(1)}^{t}\cdots e_{(s)}^{t}\) and \(e_{(s)}^{b}\cdots e_{(1)}^{b}\) are uniquely identified. We consider the case that \(x\) is \(t\). The case that \(x\) is \(b\) is similarly proved.