Background: NP-complete problems appear in a wide variety of industrial applications and
have a high number of forms, as described in various patents. The problem of finding paths avoiding
forbidden pairs of vertices which originates in graph theory is known to be NP-complete in general.
This paper focuses on an intuitive comprehension of the problem restricted to a special graph and its
Objective: It is known that a few restricted versions of the problem of finding paths avoiding forbidden
pairs of vertices are polynomial-time solvable. This paper demonstrates a seemingly simple restricted
version of the problem that, however, remains NP-complete.
Method: We show that while the problem formulation is simple, the intrinsic complexity of the restricted
version leads to an exponential solution space. Based on these insights, we construct a proof
that proves the problem is NP-complete and demonstrate that the exponential nature of the problem
stems from a related problem of building an x-y Shortest Path Tree.
Results: We devise an exact algorithm for solving the problem in exponential time and then extend
this algorithm to support arbitrary heuristics which can improve the average-case running time of the
Conclusion: The possible applications of the problem are wide, ranging from program testing and
verification to protein folding. We conclude this paper with its application in neural networks to analyse
co-activations of artificial neurons in a neural network.