This note discusses the problem of placing software monitors in programs to aid testing. It is shown that the optimal as well as the e-approximate traversal marker placement problems are NP-complete.
Maheshwari, Shachindra N., "Traversal Marker Placement Problems Are NP-Complete ; CU-CS-092-76" (1976). Computer Science Technical Reports. 90.