Restricted Version of Paths Avoiding Forbidden Pairs - Complexity and Algorithm

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 hardness. 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 algorithm. 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.