Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.