Longest increasing sequence of nodes in a graph

Recently attended a MSFT interview for SDET position.. The 2nd round interviewer asked me this question: Given a graph which has a number in the node value, find the set of all increasing sequence of vertices which are connected. Not able to recal开发者_StackOverflow社区l the exact question.. The guy seemed very hostile and was refuting each of my solutions.. Any one knowing any such question.. Finally the solution was to have an adjacency matrix.. Still not sure how this will work..

The first step is to turn the bidirectional edges into directional edges, only going from the smaller to the larger numbered node for each one. Note that the resulting graph will be a directed acyclic graph (DAG), since we can't go from a small-high-small number in a path. From here on we can ignore the node numbering.

We have now reduced the problem to the longest path problem. The solution (described in detail in the link) is to perform a topological sort on the graph and then use dynamic programming to find the longest path.

All of this can be achieved in linear time.