# Topological sort of a subgraph

If I have a graph $G$ and a subset $G'$, for all topological sorts $S$ over $G$, is there a topological sort over $G'$ that is a subset of $S$?

As a software optimization I want to pre-compute $S$ and then find the sort over $G'$ by copying all the elements of $S$ that are in $G'$ (maintaining their order, obviously).

• What about the toposort induced on $G'$ y a toposort of $G$? – Hagen von Eitzen Oct 24 '12 at 11:47
• @Eitzen for a software optimisation. I can compute the sort of $G$ ahead of time, store it in an array, and then easily find the sort of $G'$ by iterating through the array and copying the elements that are in $G'$. – ICR Oct 24 '12 at 12:07
• Why not? I mean, a topological sort is restricted by the edges present, removing these restrictions makes the original sort still valid. – Hendrik Jan Oct 24 '12 at 12:42
• @Hendrik: You could post that as an answer so that the question doesn't remain unanswered. – joriki Oct 24 '12 at 22:56
• @joriki. Thanks for the hint. Frankly I was afraid I was overlooking some details and was drawing too fast a conclusion, – Hendrik Jan Oct 25 '12 at 0:33

I would phrase it as follows. If $G$ is a graph, and $G'$ a subgraph of $G$ (on the same set of vertices), then any topological sort of $G$ is a topsort of $G'$. If $G'$ is a subgraph (perhaps loosing some vertices) then you can project on the remaining vertices to obtain a valid topsort.