On Two Problems in the Generation of Program Test Paths ; CU-CS-081-75

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