# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 4 Canonical Estimate
\(G_{(k)}\
eq G_{i}\) since \(G_{i}\) has an edge with a positive estimated length. Then, there exists a sub FJ-DAG of \(G_{i}\) that shares top and bottom vertices with \(G_{(k)}\) and has a positive length. This contradicts the assumption that \(F\) is homogeneous. Figure 8: A canonical estimate obtained by the procedure. Decrement the estimated length of every edge on the cut by one. If \(e_{i}^{t}\) (\(e_{i}^{b}\)) is saturated and \(e_{i}^{b}\) (\(e_{i}^{t}\)) is unsaturated, then increment \(\hat{w}(e_{i}^{b})\) (\(\hat{w}(e_{i}^{t})\)) by one. If both \(e_{i}^{t}\) and \(e_{i}^{b}\) are unsaturated, then increment \(\hat{w}(e_{i}^{t})\) or \(\hat{w}(e_{i}^{b})\) by one if \(\hat{w}(e_{i}^{t})=\hat{w}(e_{i}^{b})\); increment \(\hat{w}(e_{i}^{t})\) by one if \(\hat{w}(e_{i}^{t})<\hat{w}(e_{i}^{b})\); increment \(\hat{w}(e_{i}^{b})\) by one if \(\hat{w}(e_{i}^{t})>\hat{w}(e_{i}^{b})\) (see Figure 6). The following holds:  
* The estimate is still homogeneous with the same length after the update;
* By repeating this procedure, C3 eventually becomes true in \(G_{i}\);
* If \(G_{i}\) has more than one children, then the characteristic vector decreases after the update. If \(G_{i}\) has only one child, then the characteristic vector decreases or does not change after the update;
* If C2 is true in a sub FJ-DAG \(G_{(j)}\) of \(G\), then C2 is still true in \(G_{(j)}\) after the update. This is because the decrement is applied to edges on the maximum cut, and the increment is applied in such a way that C2 still holds;
* \(\hat{w}(G_{(j)})^{\uparrow}\) may decrease in some FJ-DAG \(G_{(j)}\) of \(G\). This change does not make C3 false in any sub FJ-DAG. Violation of C4: We assume C2 and C3 are true in any sub FJ-DAG. Let \(G_{i}\) be a sub FJ-DAG in which C4 is false. Then, \(\hat{w}(e_{i}^{t})>\hat{w}(G_{i})^{\downarrow}+1\) or \(\hat{w}(e_{i}^{b})>\hat{w}(G_{i})^{\downarrow}+1\) holds. Choose an unsaturated minimum cut of \(G_{i}\). Increment every edge on the cut by one. Decrement \(e_{i}^{t}\) or \(e_{i}^{b}\) by one if \(\hat{w}(e_{i}^{t})=\hat{w}(e_{i}^{b})\); decrement \(e_{i}^{t}\) by one if \(\hat{w}(e_{i}^{t})>\hat{w}(e_{i}^{b})\); decrement \(e_{i}^{b}\) by one if \(\hat{w}(e_{i}^{t})<\hat{w}(e_{i}^{b})\) (see Figure 7). The following holds:  
* The estimate is still homogeneous with the same length after the update;
* By repeating this procedure, C4 eventually becomes true in \(G_{i}\);
* The characteristic vector decreases after the update;
* If C2 is true in a sub FJ-DAG \(G_{(j)}\) of \(G\), then C2 is still true in \(G_{(j)}\) after the update. This is because the increment is applied to edges on the minimum cut, and the decrement is applied in such a way that C2 still holds;
* \(\hat{w}(G_{(j)})^{\uparrow}\) may decrease in some FJ-DAG \(G_{(j)}\) of \(G\). This change does not make C3 false in any sub FJ-DAG;
* \(\hat{w}(G_{(j)})^{\downarrow}\) may increase in some FJ-DAG \(G_{(j)}\) of \(G\). This change does not make C4 false in any sub FJ-DAG;
* When \(\hat{w}(G_{i})^{\uparrow}=\hat{w}(G_{i})^{\downarrow}\), \(\hat{w}(G_{i})^{\uparrow}\) increases and C3 may become false. We show that this does not happen. Since C3 is true in \(G_{i}\) before the update, \(\hat{w}(e_{i}^{t})\geq\hat{w}(G_{i})^{\uparrow}\) (\(\hat{w}(e_{i}^{b})\geq\hat{w}(G_{i})^{\uparrow}\)) holds if \(e_{i}^{t}\) (\(e_{i}^{b}\)) is unsaturated. Suppose that \(e_{i}^{t}\) is updated. By the procedure, \(\hat{w}(e_{i}^{t})\geq\hat{w}(e_{i}^{b})\) holds before the update. If \(e_{i}^{b}\) is saturated, then C3 is still true after the update. Suppose that \(e_{i}^{b}\) is unsaturated. Then, \(\hat{w}(e_{i}^{t})\leq\hat{w}(e_{i}^{b})+1\) holds by C2. Since \(\hat{w}(e_{i}^{t})>\hat{w}(G_{i})^{\downarrow}+1=\hat{w}(G_{i})^{\uparrow}+1\) before the update, \(\hat{w}(e_{i}^{t})\geq\hat{w}(G_{i})^{\uparrow}\) holds after the update. Moreover, \(\hat{w}(e_{i}^{b})+1\geq\hat{w}(e_{i}^{t})>\hat{w}(G_{i})^{\uparrow}+