
Depth-First Dynamic Programming (DP).
Topological orders are generated in a depth-first manner (with backtracking) where next node is picked randomly among available candidates. Branch exploration is terminated if 1) the same set of nodes are in the partial sequence as a branch that has been already explored - only the lowest cost partial sequence is retained (dynamic programming approach), and 2) if the current partial cost is already higher than the lowest cost of any full sequence already found (cost increases monotonically). This algorithm will eventually find the global optimal order, though the run time for doing so is expected to be at least exponential in |V| [1]}; it is however able to return at least one complete sequence in time \(O(|V| + |E|)\)  [2]} in the worst case, same as DFS.
In our implementation, we set a wall time of one hour and pick the best complete path found. We observe that for our synthetic layered graphs, if the graph size is as small as \(|V|=100\) , we can actually find the optimal sequence in most cases within the one hour budget. We ran this algorithm on a CPU machine with Intel(R) Xeon(R) W-2123 CPU @ 3.60GHz

Approximate DP.
We define the state space \(S\)  as the space including a set of all nodes for each partial sequence (which ignores the ordering information) and the action space for each state as the space of all possible next-node choices at that state (based on the topological structure). As an example for the state representation, if there is a partial sequence \(5\rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 1\) , the corresponding state is \(\lbrace 1, 2, 3, 4, 5\rbrace \) .
With the empty set \(\emptyset \)  being an initial state (meaning that no node has been added), we consider a state transition model that adds an action (a node) to a state and creates a successor state. Specifically, we can partition \(S\)  into \(S_0\cup S_1\cup \cdots \cup S_{|V|}\) , where \(S_t\)  is the space including a set of all nodes for each length-\(t\)  partial sequence (note that \(S_0=\lbrace \emptyset \rbrace \) ). At every iteration \(t=0, 1, ..., |V|-1\) , the algorithm takes \(S_t\)  and assumes that we have (1) the minimum cost and (2) the best partial sequence for each state in \(S_t\) , where the minimum cost is over all feasible partial sequences corresponding to the state. Then, for each successor state in \(S_{t+1}\) , the algorithm computes the minimum cost and the best partial sequence for reaching out that state.
It should be noted that the algorithm gives an exact solution if the amount of time and memory resource is sufficient, e.g., an exact solution can be found for 100-node graphs. However, due to the practical resource limitation, we only keep top-\(K\)  elements of \(S_{t+1}\)  for each iteration \(t\)  based on costs. We use the beam size \(K=100,000\)  for all experiments, and Nvidia Tesla V-100 is used for parallel computation across multiple states for each iteration.

