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 fo rmal-language-constrained shortest/simple path problem consists of finding a shortest (simple) path p in G complying with the additional constraint th at l(p) is an element of L. Here l(p) denotes the unique word obtained by c oncatenating the Sigma-labels of the edges along the path p. The main contr ibutions of this paper include the following: (1) We show that the formal-language-constrained shortest path problem is s olvable 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 f ixed simple regular languages and to very simple classes of graphs (e.g., c omplete 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 d estination is solvable in polynomial time and (ii) the extension to finding CFL-constrained simple paths is NP-complete. Our results extend the previo us results in [SIAM J. Comput., 24 (1995), pp. 1235-1258; Proceedings of th e 76th Annual Meeting of the Transportation Research Board, 1997; and Proce edings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Database Systems, 1 990, pp. 230-242]. Several additional extensions and applications of our re sults 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 algo rithm was given by [Proceedings of the 76th Annual Meeting of the Transport ation Research Board, 1997] and takes exponential time in the worst case.