In this paper we analyze the complexity of algorithms for two problems that arise in automatic test path generation for programs: the problem of building a path through a specified set of flow graph nodes and the problem of building a path which satisfies impossible-pairs restrictions in a flow graph. We give a highly efficient algorithm for the first problem, and show that the second problem is NO-complete in the sense of Cook and Karp.
Gabow, Harold N.; Maheshwari, Sachindra N.; and Osterweil, Leon J., "On Two Problems in the Generation of Program Test Paths ; CU-CS-081-75" (1975). Computer Science Technical Reports. 79.