If I have a set of nodes N and a set of vertices V_1 that define a graph G_1 with a certain topological order, how can I check whether a subset of nodes from N and a new set of vertices V_2 that define a graph G_2 maintain the topological order of G_1?
e.g.
G_1:
D -> E
B -> C
A -> C
A topological ordering of G_1: [A, B, C, D, E]
G_2:
D -> B
B -> E
The topological ordering of G_2: [D, B, E]
I was thinking of some sort of brute force approach where I generate all topological orderings of G_1, remove the nodes not found in G_2 from those orderings and check if any match the first ordering found of G_2.
Is my potential solution correct? Do you have any better suggestions?
I think your solution is correct, but it's inefficient.
For some bad cases (G_2 is a cycle so there's no topological ordering and G_1 has no edges so any ordering is topological) you end up doing O(N!*N).
A better solution is to compute a topological order that satisfies both graphs.
In the standard topological sort algorithm you keep count of incoming edges. At each step you pick a node that has a count of 0, add it to the solution, decrease the count for all outgoing edges and continue until either there's no more nodes to pick or all have non-zero count (a cycle).
What I suggest is that you keep two sets of counts for the two graphs. Pick a node that has a count of 0 in both sets (that is, is a valid next choice in both graphs) and update the counts in both graphs according to their outgoing links. If you finish all the nodes then you've found a ordering that is a topological sort for both graphs, otherwise there's no such ordering.
If you can, you can also merge the two graphs and compute a topological sort on the merged graph using the standard algorithm. The result (if any) should be a valid topological sort for both original graphs.
Both solutions (if implemented correctly) will have a complexity of O(N).