Topological sort with an objective function

Question

I have a DAG with N nodes, i.e., 1, 2, ..., N, and each node has a weight (we can call it time) x_1, x_2, ..., x_N. I want to do a topological sorting but the difficulty is that I have an objective function when sorting. My objective function is to minimize the total time between several pairs of nodes.

For example, I have a DAG with 6 nodes, and I want a specific topological sorting such that (1,3) + (2,4) is minimized, where (A,B) denotes the time between two nodes A and B. For instance, if we have a sort [1, 6, 3, 2, 5, 4, 7], (1,3) = x_6 and (2,4) = x_5. Based on the DAG, I want to find a sorting that minimizes (1,3) + (2,4).

I have been thinking this problem for a while. Generate all possible topological sorts (reference link) and calculate the objective function one by one is always a possible solution but it takes too much time if N is large. I was also suggested to use branch-bound pruning when generating all possible sorts (I am not very familiar branch-bound but I think that won't dramatically reduce the complexity).

Any (optimal or heuristic) algorithm for this kind of problem? It would be perfect if the algorithm can also be applied to other objective functions such as minimizing the total starting time for some nodes. Any suggestion is appreciated.

PS: Or alternatively, is it possible to formulate this problem as a linear integer optimization problem?

Answer 1

One way to solve this is as follows:

First we run All-Pairs shortest path algorithm Floyd-Warshall. This algorithm can be coded in essentially 5 lines of code and it runs in O(V^3) time. It generates the shortest paths between each of the pair of vertices in the graph, i.e., it generates V X V matrix of shortest paths as its output.

It's trivial to modify this algorithm so that we can also get the count of vertices included in each of the O(N^2) paths. So now we can eliminate all paths that have less than N vertices. For the remaining paths, we order them by their cost and then test each of them to see if topological sort property is not violated. If this property is not violated then we have found our desired result.

The last step above, i.e., testing topological sort can be performed in O(V+E) for each of the O(V^2) paths. This yields worst case runtime of O(V^4). However in practice this should be fast because Floyd-Warshall can be made very cache friendly and we would be testing only small fraction of O(N^2) paths in reality. Also if your DAG is not dense then you might be able to optimize topological testing as well with appropriate data structures.