Finding a simple path with multiple must-include nodes

This document presents an algorithm to find a simple path in the given network with multiple must-include nodes. The problem of finding a simple path with only one must-include node can be solved in polynomial time using lower bound max-flow approach. However, including multiple nodes in the path has been shown to be a NP-Complete. This problem may arise in network areas such as forcing the route to go through particular nodes, which have wavelength converter (optical), have monitoring provision (telecom), have gateway functions (in OSPF) or are base stations (in MANET). Also, network standards allow loose definition of routing by requiring one or more nodes to be in the routing of Link State Packet. In this document, a heuristic algorithm is described to find a simple path between a pair of terminals, which has constraint to pass through a certain set of other nodes. The algorithm is comprised into two main steps: (1) considering a pair of nodes in sequence from source to destination as a segment and then computing candidate paths between each segment, and (2) combining paths, one from each segment, in order to make simple path from source to destination. The max-flow approach is used to find candidate paths, a which provides maximum number of edge disjoint paths for individual segments. The second step of the algorithm uses backtracking algorithm for combining paths. The time complexity of the first step of the algorithm is O(kiVIIEI 2 ), where k is the number of must-include nodes. The time complexity of step (2) depends upon total number of candidate paths which are not touching any one of the candidates of other segments. So, the worse case time complexity of step (2) is O(.Ak), where .A is the maximum nodal degree of the network. However, we show that step (2) has minimal effect on the algorithm and it does not grow exponentially with k in this application. Later, we also show that initial re-ordering of the given sequence of must-include nodes can improve the result. The experimental results show that the algorithm is successful in computing near optimal path in reasonable time. keywords: constrained path computation, graph theory, heuristic algorithm, max flow, network route.