Constrained/Optimal Topological Order to enhance/reduce the performance/memory usage of other algorithms
I originally posted this question here
Lets assume we have a highly connected directed acyclic graph (DAG, more edges then nodes). Since it is a DAG, we can retrieve a topological order of nodes to traverse the graph with different algorithms. Lets assume we want to traverse it in a dynamic programming approach to retrieve a specific statistic X.
Using the topological order, the dynamic approach would consume up to M much memory, which can be traced by a concept of opened nodes thorughout the traversal:
By iterating over the top. order, a node is open if it has at least one edge from a node which already was visited by the topological order. It is closed (or not open) if it gets visited.
Pseudo-Code:
opened_nodes = list(Boolean(False)), #num_of_nodes)
opened_nodes[top_order[0]] = True // Initial
pos_at_top_order = list(Integer, #num_of_nodes)
for each n, n_idx in top_order:
opened_nodes[n] = False
for each edge in out_going_edge(n):
true_list[edge.target = True
pos_at_top_order[n_idx] = sum_of_all_trues(opened_nodes)
return pos_at_top_order
(here for the topological order, it can be adjusted for the rev. Top. order)
A goal here would be to reduce the memory usage M of the dynamic programming approach. To achieve this, the top. 180
order can be manipulated and with the Pseudo-Code we could somehow track, whether the top. order is better or worse then another.
Now to my question: Is there a way to directly retrieve such a top. Order so that M gets minimal, or could this be a NP-hard (or NP-complete) problem? What about some hard limits like: only retrieve the top. orders where the M is smaller/higher then a set amount of memory usage.
Is there any literature about such a "optimization"? Which search terms could be used to search for this e.g. in Scholar?
I already tried some different generation methods of top. order (in total 9) All of them look similar to the curves in the figure: (here i used igraphs top sorting algorithm and <PERSON> algorithm with some variations. Not shown but i also tried: DFS- and some "BFS" approaches. This is a highly connected graph, containing 14207 nodes and 94113 edges.)
Any input on this is highly appreciated! 180