On locating a single path-like facility in a general graph

The problem of locating a path-like facility of fixed length in a tree can be solved in polynomial time. However, this problem is NP-complete even on very sparse graphs such as outerplanar graphs. We show that if the length of the facility to be located is small then the corresponding path location problem can be solved efficiently. We suggest O(n⁴ log n) and O(n⁴) algorithms to solve the problem of locating small paths with minmax and minsum criteria on a general graph. We also give a method to solve small path location problems with a general nonlinear objective function. If the path-like facility to be located is known to be contained in some path with at most r nodes then we show that, for fixed r, the path location problem is solvable in polynomial time.