Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal language L ⊆ Σ*, 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) ∈ L. Here l(p) denotes the unique word obtained by concatenating the Σ-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 Reasearch 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. © 2000 Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/S0097539798337716Cite as:
@article{Barrett_2000,
doi = {10.1137/s0097539798337716},
url = {https://doi.org/10.1137%2Fs0097539798337716},
year = 2000,
month = {jan},
publisher = {Society for Industrial {&} Applied Mathematics ({SIAM})},
volume = {30},
number = {3},
pages = {809--837},
author = {Chris Barrett and Riko Jacob and Madhav Marathe},
title = {Formal-Language-Constrained Path Problems},
journal = {{SIAM} Journal on Computing}
}