Formal-language-constrained path problems

Given an alphabet Sigma, a (directed) graph G whose edges are weighted and Sigma-labeled, and a formal language L subset of or equal to Sigma*, the formal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional constraint that l(p) is an element of L. Here l(p) denotes the unique word obtained by concatenating the Sigma-labels of the edges along the path p. The main contributions of this paper include the following: (1) We show that the formal-language-constrained shortest path problem is solvable efficiently in polynomial time when L is restricted to be a context-free language (CFL). When L is specified as a regular language we provide algorithms with improved space and time bounds. (2) In contrast, we show that the problem of finding a simple path between a source and a given destination is NP-hard, even when L is restricted to fixed simple regular languages and to very simple classes of graphs (e.g., complete grids). (3) For the class of treewidth-bounded graphs, we show that (i) the problem of finding a regular-language-constrained simple path between source and destination is solvable in polynomial time and (ii) the extension to finding CFL-constrained simple paths is NP-complete. Our results extend the previous results in [SIAM J. Comput., 24 (1995), pp. 1235-1258; Proceedings of the 76th Annual Meeting of the Transportation Research Board, 1997; and Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Database Systems, 1990, pp. 230-242]. Several additional extensions and applications of our results in the context of transportation problems are presented. For instance, as a corollary of our results, we obtain a polynomial-time algorithm for the best k-similar path problem studied in [Proceedings of the 76th Annual Meeting of the Transportation Research Board, 1997]. The previous best algorithm was given by [Proceedings of the 76th Annual Meeting of the Transportation Research Board, 1997] and takes exponential time in the worst case.