# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 4 Canonical Estimate
We make the following observations:  
* The estimated length of the subpath \[e_{(s+1)}^{t}\cdots e_{(r)}^{t}e_{(r)}^{b}\cdots e_{(s+1)}^{b}\] in \(G_{(s)}\) is uniquely determined; [by the fact that \(F\) gives the unique estimated length to goal paths of \(G_{(s)}\) as shown above]
* \(\hat{w}(G_{i})^{\downarrow}\leq\hat{w}(e_{(s)}^{b})\leq\hat{w}(G_{i})^{ \downarrow}+1\) if \(w(e_{(s)}^{b})>\hat{w}(G_{i})^{\downarrow}\); \(\hat{w}(e_{(s)}^{b})=w(e_{(s)}^{b})\leq\hat{w}(G_{i})^{\downarrow}\) otherwise; [by the fact that \(e_{(s)}^{t}\) is on a minimum unsaturated cut of \(G_{i}\) (This exclude that case \(\hat{w}(e_{(s)}^{t})>\hat{w}(e_{(s)}^{b})\)), \(\hat{w}(e_{(s)}^{t})=\hat{w}(G_{i})^{\downarrow}\) as we have assumed, and C2]
* \(\hat{w}(G_{i})^{\downarrow}\leq\hat{w}(e_{(j)}^{x})\leq\hat{w}(G_{i})^{ \downarrow}+1\) if \(w(e_{(j)}^{x})>\hat{w}(G_{i})^{\downarrow}\); \(\hat{w}(e_{(j)}^{x})=w(e_{(j)}^{x})\leq\hat{w}(G_{i})^{\downarrow}\) otherwise (\(x\) is \(t\At this moment, the current estimate is the minimum estimate that satisfies all the properties. If the length of \(\pi\) is \(h\), then halt;
3. From outmost unsaturated edges \(e^{t}_{(j)}\) and \(e^{b}_{(j)}\), increment the estimated length by one until the length of \(\pi\) reaches \(h\). Figure 8 shows an estimate obtained by this procedure, where \(s=5\). When the procedure terminates, \(\hat{w}(e^{t}_{(1)})\) and \(\hat{w}(e^{b}_{(1)})\) are unique up to their exchange. Let \(G\) be an FJ-DAG. Any canonical estimate for \(G\) with length \(h\) has the same characteristic vector. Proof. : Let \(F\) be a canonical estimate for \(G\), as shown in Figure 4. The proposition is obvious when \(level(G)=0\). Suppose that \(level(G)>0\). We can consider each \(i\) separately. By Lemma 2, \(\hat{w}(e^{t}_{i})\) and \(\hat{w}(e^{b}_{i})\) are unique up to their exchange. Therefore, the length of \(F\) in \(G_{i}\) is also the same in any canonical estimate. By the induction hypothesis, any canonical estimate for \(G_{i}\) has the same characteristic vector, and therefore any canonical estimate for \(G\) has the same characteristic vector as well. Let \(F\) be any homogeneous estimate for \(G\) with length \(h\). Then, there exists a canonical estimate \(F^{*}\) with the same length \(h\) and \(\#_{F^{*}}\preceq\#_{F}\). Proof. : If a homogeneous estimate is not canonical, then at least one of C2, C3, and C4 is not true in some sub FJ-DAG of \(G\). We introduce procedures to make the estimate canonical. Violation of C2: Let \(G_{i}\) be a sub FJ-DAG in which C2 is false. This means that \(e^{t}_{i}\) (\(e^{b}_{i}\)) is unsaturated and \(\hat{w}(e^{b}_{i})>\hat{w}(e^{t}_{i})+1\) (\(\hat{w}(e^{t}_{i})>\hat{w}(e^{b}_{i})+1\)). Then, increment \(\hat{w}(e^{t}_{i})\) (\(\hat{w}(e^{b}_{i})\)) by one and decrement \(\hat{w}(e^{b}_{i})\) (\(\hat{w}(e^{t}_{i})\)) by one (see Figure 5). The following holds:  
* The estimate is still homogeneous with the same length after the update;
* By repeating this procedure, C2 eventually becomes true in \(G_{i}\);
* The characteristic vector decreases after the update;
* If C2 is true in another sub FJ-DAG \(G_{(j)}\) of \(G\), then C2 is still true in \(G_{(j)}\) after the update. Violation of C3: We assume C2 is true in any sub FJ-DAG. Let \(G_{i}\) be a sub FJ-DAG in which C3 is false. Then, \(e^{t}_{i}\) (\(e^{b}_{i}\)) is unsaturated and \(\hat{w}(e^{t}_{i})<\hat{w}(G_{i})^{\uparrow}\) (\(\hat{w}(e^{b}_{i})<\hat{w}(G_{i})^{\uparrow}\)). Choose a maximum cut of \(G_{i}\). Then, the cut contains an edge with estimated length \(\hat{w}(G_{i})^{\uparrow}>0\). We claim that every edge on this cut has a positive estimated length. This is proved as follows. Assume that the cut has an estimated length of \(0\). Since the cut is maximum, there exists a sub FJ-DAG of \(G_{i}\) with top and bottom edges in which all edges have an estimated length of \(0\) (the minimal case is a single vertex with top and bottom edges). Let \(G_{(k)}\) be a maximal such sub FJ-DAG of \(G_{i}\).