1
$\begingroup$

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).

  • 0
    @joriki. Thanks for the hint. Frankly I was afraid I was overlooking some details and was drawing too fast a conclusion,2012-10-25

1 Answers 1

3

Why not? I mean, a topological sort is restricted by the edges present, removing these restrictions makes the original sort still valid.

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.