Restricted Version of Paths Avoiding Forbidden Pairs – Complexity and Algorithm

Author(s): Eva Milková*, Karel Petránek.

Journal Name: Recent Patents on Computer Science

Volume 10 , Issue 2 , 2017

Become EABM
Become Reviewer

Graphical Abstract:


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.

Rights & PermissionsPrintExport Cite as

Article Details

VOLUME: 10
ISSUE: 2
Year: 2017
Page: [116 - 121]
Pages: 6
DOI: 10.2174/2210683905666170125100548
Price: $58

Article Metrics

PDF: 13
HTML: 1
EPUB: 1
PRC: 1