graph algorithms figure depth-first search of gr --strong components are { }{hij}{bacf}{ }{eto prove that this algorithm workswe must show that if two vertices and are in the same depth-first spanning tree of gr there must be paths from to and from to equivalentlywe can show that if is the root of the depth-first spanning tree of gr containing vthen there is path from to and from to applying the same logic to would then give path from to and from to these paths would imply paths from to and to (going through xsince is descendant of in gr ' depth-first spanning treethere is path from to in gr and thus path from to in furthermoresince is the rootx has the higher postorder number from the first depth-first search thereforeduring the first depth-first searchall the work processing was completed before the work at was completed since there is path from to xit follows that must be descendant of in the spanning tree for --otherwise would finish after this implies path from to in and completes the proof introduction to np-completeness in this we have seen solutions to wide variety of graph theory problems all these problems have polynomial running timesand with the exception of the network flow problemthe running time is either linear or only slightly more than linear ( (|elog | |)we have also mentionedin passingthat for some problems certain variations seem harder than the original recall that the euler circuit problemwhich finds path that touches every edge exactly onceis solvable in linear time the hamiltonian cycle problem asks for simple cycle that contains every vertex no linear algorithm is known for this problem the single-source unweighted shortest-path problem for directed graphs is also solvable in linear time no linear-time algorithm is known for the corresponding longestsimple-path problem the situation for these problem variations is actually much worse than we have described not only are no linear algorithms known for these variationsbut there are no known algorithms that are guaranteed to run in polynomial time the best known algorithms for these problems could take exponential time on some inputs