# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 5 A Solution to PFJUEL
In any sub FJ-DAG that does not contain \(e_{i}^{t}\), C3 and C4 are still true after the update. Thus, we need to check the conditions for sub FJ-DAGs that contain \(e_{i}^{t}\). Let \(G_{(j)}\) be such a sub FJ-DAG. Then, \(\hat{w}(G_{(j)})^{\uparrow}\) and \(\hat{w}(G_{(j)})^{\downarrow}\) may be incremented by one. Suppose that \(\hat{w}(G_{(j)})^{\uparrow}\) is incremented. This occurs when \(\hat{w}(e_{i}^{t})=\hat{w}(G_{(j)})^{\uparrow}\) just before the update. C3 becomes false after the update only if for the top or bottom edge \(e_{(j)}^{x}\) of \(G_{(j)}\), \(\hat{w}(e_{(j)}^{x})=\hat{w}(e_{i}^{t})\) holds just before the update. Every goal path that contains \(e_{i}^{t}\) also contains \(e_{(j)}^{x}\) because \(e_{(j)}^{x}\) is in a level higher that that of \(e_{i}^{t}\). Therefore, SPIOE does not choose \(e_{i}^{t}\) by line 10, and this case does not occur. Clearly, C4 is still true when \(\hat{w}(G_{(j)})^{\downarrow}\) is incremented. Thus, C3 and C4 are still true in other sub FJ-DAGs. By the above arguments, C2-C4 are still true in all sub FJ-DAGs after the update. Hence, we can conclude that the obtained estimate is canonical. The condition at line 4-5 is not used in the above proof. Dropping this condition may cause waste fail calls and unnecessary success calls. From Corollary 1 and Lemma 4, we obtain the main theorem. If waste fail calls do not occur, then SPIOE always gives an optimal estimate. The detailed complexity analysis of the SPIOE is omitted for the following reasons. The analysis can be done for (i) the characteristic vector of the optimal terminal estimate obtained by SPIOE and (ii) the total computational time of SPIOE. The optimal terminal estimate is characterized by Corollary 1 (i.e., canonical estimate) and is determined by the given FJ-DAG. It may be possible to give trivial lower/upper bounds of the characteristic vector, but they are meaningless. The total computational time of SPIOE is obtained by evaluating operations in each iteration and the total number of iterations. Operations in each iteration consist of maintaining shortest goal paths and finding an edge with the minimum estimated length in the highest level. They can be done in polynomial time. Furthermore, we can give an upper bound of the number of iterations, which is determined by the optimal terminal estimates. This is apparently polynomial in the size of the graph and edge length. Such detailed complexity analysis is not very valuable under the above cost assumption on calling oracles. Moreover, the goal of the paper is to develop an optimal strategy that can be applied to real problems. In this sense, the goal has been achieved. Finally, we analyze the number of waste fail calls. Let \(h^{*}\) be the length of the shortest goal path. We introduce a special class of strategies. Strategies that always issue oracle calls to unsaturated goal paths with the shortest estimated length are called rational. In the terminal estimate obtained by any rational strategy, the estimated length of every goal path is always less than or equal to \(h^{*}+1\), and therefore the number of waste fail calls is less than the number of goal paths. Let \(g\) be the number of goal paths. Then, \(g-1\) is an upper bound of the number of waste fail calls by any rational strategy. For a strategy that is not rational, the estimated length of some goal path may become greater than \(h^{*}+1\). Suppose that the estimated length of the current shortest goal path has reached \(h^{*}\) and the strategy issues an oracle call to a goal path with length \(h^{*}+1\). We can make an instance of FJ-DAGs for which the oracle call fails and the estimated length becomes \(h^{*}+2\). There exists an FJ-DAG for which any rational strategy gives \(g-1\) waste fail calls; i.e., \(g-1\) is the tight upper bound for rational strategies. Let us consider an FJ-DAG shown in Figure 9, where every edge has length 1. At each round, any rational strategy picks up one unsaturated edge on a goal path with the shortest estimated length and issues an oracle call to it.