Eva Milková and Karel Petránek Pages 116 - 121 ( 6 )
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.
NP-complete problem, path avoiding forbidden pairs of vertices, free path problem algorithm, Shortest Path Tree, arbitrary heuristics.
Department of Informatics, Faculty of Science, University of Hradec Králové, Czech Republic, Rokitanského 62, 500 00 Hradec Králové, Faculty of Science, University of Hradec Králové, Rokitanského 62, 500 00 Hradec Králové