# A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
## 2 Problem Formulation  
We first formally define a class of graphs called fork-join directed acyclic graphs (FJ-DAGs). An FJ-DAG is a directed acyclic graph \(G=(V,E)\), where \(V\) is the set of vertices and \(E\subseteq V\times V\) is the set of edges, with two special vertices the top vertex \(v^{t}\in V\) and the bottom vertex \(v^{b}\in V\). We denote \(G=(V,E,v^{t},v^{b})\) to indicate the two special vertices. Definition 1: FJ-DAGs are recursively defined as follows:  
1. A single vertex \(G=(\{v\},\emptyset,v,v)\) is an FJ-DAG;
2. Let \(G_{i}=(V_{i},E_{i},v^{t}_{i},v^{b}_{i}),\ i=1,\cdots,m\) be FJ-DAGs. Then, the graph \[G=\left(\bigcup_{i}^{m}V_{i}\cup\{v^{t},v^{b}\},\bigcup_{i}^{m}E_{i}\cup\{( v^{t},v^{t}_{i}),(v^{b}_{i},v^{b})\mid i=1,\cdots,m\},v^{t},v^{b}\right)\] is an FJ-DAG, where \(v^{t}\) and \(v^{b}\) do not belong to any \(V_{i}\). Each \(G_{i}\) is called a child of \(G\);
3. No other graphs defined as above are not FJ-DAGs. Each edge \(e^{t}_{i}=(v^{t},v^{t}_{i})\) is called a top edge of \(G\) and each edge \(e^{b}_{i}=(v^{b}_{i},v^{b})\) is called a bottom edge of \(G\). An FJ-DAG has a nested structure. We introduce the level of an FJ-DAG \(G\), denoted by \(level(G)\), as follows: (i) the level of a single vertex \(G\) is 0; (ii) if \(G_{i},i=1,\cdots,m\) are children of \(G\), then \(level(G)=\max_{i}\ level(G_{i})\). Any FJ-DAG contained in an FJ-DAG \(G\) as a subgraph is called a sub FJ-DAG of \(G\). Figure 1 shows an FJ-DAG,where the level of each sub FJ-DAG is indicated. We also define the level of each edge. The level of an edge is defined as the level of a sub FJ-DAG that contains the edge as a top or bottom edge. Such a class of graphs is well studied in the research field of queuing networks since it appears in various applications such as parallel computing and flexible manufacturing systems [17]. In an FJ-DAG \(G=(V,E,v^{t},v^{b})\), a path from \(v^{t}\) to \(v^{b}\) is called a goal path of \(G\). Now, we define a graph problem, Pathfinding in an FJ-DAG with Unknown Edge Length (PFJUEL), as follows:  
Given  
An FJ-DAG \(G=(V,E,v^{t},v^{b})\);  
Oracle \(search_{c}(v_{i},v_{j})\): given two vertices \(v_{i}\), \(v_{j}\) and a nonnegative integer \(c\), the oracle answers whether the length of edge \((v_{i},v_{j})\) is less than or equal to \(c\) or not. Assumption  
Each edge has a nonnegative integer length, but the length is unknown in advance and should be found by calling the oracle. Find  
A shortest goal path. PFJUEL is an online problem since the length of each edge is known only by calling oracles. As we have mentioned in the introduction, any procedures that solve such an online problem should be adaptive; i.e., the next action (i.e., an oracle call) to be taken is determined by the current knowledge of the target. Such a procedure is called a strategy. Roughly speaking, the objective of PFJUEL is to find a strategy that is optimal for the total cost of oracle calls. The formal statement of an optimal strategy to PFJUEL is given after we introduce the required concepts and terminology. We note that PFJUEL is a generalization of the problem [PERSON] studied in [1]. The targets of PSTUEL are directed trees. Given a directed tree, we can make an FJ-DAG such that the shortest goal path of the FJ-DAG contains the shortest goal path of the directed tree, where a goal path of a tree is a path from the root to a leaf. To do this, we add edges with length 0 so that the tree becomes an FJ-DAG (Figure 2). At some step of a strategy for PFJUEL, the set of edges \(E\) is partitioned into two sets \(E_{K}\) and \(E_{U}\), where the length \(w(v_{i},v_{j})\) of each edge \((v_{i},v_{j})\in E_{K}\) is already known, and the length of each edge in \(E_{U}\) is unknown. An edge \((v_{i},v_{j})\) moves from \(E_{U}\) to \(E_{K}\) when its length has been found. Moreover, for each edge \((v_{i},v_{j})\in E_{U}\), a lower bound \(\hat{w}(v_{i},v_{j})\) of the edge length is obtained by previous oracle calls.