Abstract
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.Keywords: NP-complete problem, path avoiding forbidden pairs of vertices, free path problem algorithm, Shortest Path Tree, arbitrary heuristics.
Graphical Abstract
Related Books
Challenges and Opportunities for Deep Learning Applications in Industry 4.0
Recent Advances in IoT and Blockchain Technology
Augmented Intelligence: Deep Learning, Machine Learning, Cognitive Computing, Educational Data Mining
Human-Computer Interaction and Beyond: Advances Towards Smart and Interconnected Environments Part II
Machine Learning and Its Application: A Quick Guide for Beginners
Computational Intelligence For Data Analysis
Applied Machine Learning and Multi-Criteria Decision-Making in Healthcare
Advanced Computing Techniques: Implementation, Informatics and Emerging Technologies
How to Design Optimization Algorithms by Applying Natural Behavioral Patterns
Human-Computer Interaction and Beyond: Advances Towards Smart and Interconnected Environments (Part I)
13
1
1
1