Formal language constrained path problems

Catherine Barrett, Riko Jacob, Madhav MaratheUniversity 1997

Abstract

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.

Introduction

Standard navigation algorithms, like Dijkstra’s, are highly effective at finding the shortest route based on distance or cost. However, real-world routing often involves complex logical constraints. For example, in intermodal transportation, a traveler might specify: "I want to walk to a station, take any number of trains, and then walk to my office."

In computer science terms, this means the sequence of "labels" on the edges of a path must belong to a specific formal language. This paper explores the computational complexity of two main problems:

  1. Constrained Shortest Path (SHP): Find the path with the minimum weight that satisfies the language constraint (loops are allowed).
  2. Constrained Simple Path (SiP): Find the path with the minimum weight that satisfies the constraint and never visits the same node twice.
The original paper title page from Los Alamos National Laboratory.

Methods and Complexity

The authors categorize these problems based on the Chomsky Hierarchy of languages: Regular (simplest), Context-Free (CFL), and Context-Sensitive (most complex).

Algorithmic Techniques

  • Product Graphs: To solve SHP with Regular Language constraints, the authors construct a "product graph" combining the original network with a Nondeterministic Finite Automaton (NFA).
  • Dynamic Programming (DP): For CFLs, they adapt parsing logic (similar to the CYK algorithm) to graph traversal, defining a recurrence relation that builds paths from smaller sub-paths based on grammar rules.
  • Complexity Reductions: To prove that finding "simple" paths is hard, they use reductions from known difficult problems like 3SAT and the Hamiltonian Path problem.
  • Treewidth Analysis: They investigate "treewidth-bounded" graphs—graphs that are "tree-like"—to show that some otherwise impossible problems become solvable in polynomial time when the graph structure is restricted.

Key Insights

  • The Loophole: In a standard graph, the shortest path is usually a simple path. However, under language constraints, the shortest path might require a loop. For example, if a rule requires exactly five 'a' labels, a traveler might need to circle a block to satisfy the grammar.
  • The Complexity Gap: There is a massive "complexity cliff" between shortest paths and simple paths. SHP with CFL constraints is solvable in polynomial time ($P$), but finding a simple path with even a basic Regular constraint is NP-hard on general graphs and even grids.
  • Treewidth as a Buffer: The "tree-likeness" of a graph (treewidth) is a key factor. If a graph is tree-like, regular-constrained simple path problems become efficient, though CFL constraints remain NP-complete.

Results and Applications

  • Shortest Path (SHP): Regular constraints are solvable in $O(|R||G| \log(|R||G|))$ time, while CFL constraints remain polynomial.
  • Simple Path (SiP): Regular constraints are NP-hard on general graphs but polynomial on treewidth-bounded graphs.
  • Practical Application: The research provided a new polynomial-time algorithm for the "Best k-Similar Path" problem, improving upon previous exponential-time methods. This work was motivated by the TRANSIMS (TRansportation ANalysis and SIMulation System) project at Los Alamos National Laboratory, which simulates large-scale urban transportation networks.

Limitations

While the algorithms for treewidth-bounded graphs are technically polynomial, the authors note that the underlying DP tables are intricate, suggesting high constant factors for practical implementation. Future work is needed to find more specific classes of graphs or types of queries that allow for efficient real-world computation in large-scale systems.

Summary updated

Abstract

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.
BibTeX
@inproceedings{barrett1997formal,
  author = {Catherine Barrett and Riko Jacob and Madhav Marathe},
  title = {{Formal language constrained path problems}},
  booktitle = {University},
  year = {1997},
}
Figure