Abstract
This paper explores the Generalized Parametric Path Problem (GPP), where edge weights are functions of an input parameter. By mapping the boundary between tractability and NP-hardness, the authors demonstrate that while scalar linear problems are solvable in polynomial time without FIFO assumptions, the introduction of multiple parameters or non-linearity leads to computational hardness.
Introduction
In traditional shortest-path problems, edge weights are static. However, real-world applications like transportation and finance require modeling costs that vary with state or time. For instance, travel time across a network depends on the departure time, and financial returns depend on fluctuating exchange rates.
A common simplification in time-dependent routing is the First-In-First-Out (FIFO) property, which assumes that an earlier departure always guarantees an earlier arrival. However, real-world scenarios often violate this (e.g., Braess’ Paradox). The Generalized Parametric Path Problem (GPP) addresses these complexities by allowing for non-FIFO behavior and multi-dimensional parameters.
Methods: Algorithmic Design and Complexity
The authors investigate the scalar linear case using a modified Bellman-Ford-Moore approach. Standard algorithms only track the minimum cost, but linear functions with negative slopes can cause a "minimum" value at one stage to become a "maximum" later. To account for this "flip factor," the proposed algorithm tracks both the minimum ($r_{\min}$) and maximum ($r_{\max}$) costs at each node.
Beyond algorithmic design, the paper employs complexity theory to establish hardness results. By reducing known NP-hard problems like SET PARTITION to specific GPP variants, the authors identify a "complexity cliff" where adding a second parameter or using piecewise linear functions makes the problem intractable.
Key Insights and Results
The research yields several significant findings regarding the structure of optimal paths:
- Tractability of Scalar Linear GPP: The problem remains solvable in $O(n^3)$ time by tracking both cost envelopes, even without FIFO assumptions.
- Quasi-Polynomial Path Complexity: The number of optimal paths in a non-FIFO network is bounded by $n^{O(\log n)}$, generalizing results previously thought to be restricted to FIFO networks.
- The Complexity Cliff: While one-parameter linear problems are efficient, GPP becomes NP-hard to approximate when weight functions are piecewise linear, quadratic, or involve two or more parameters.
- Compositional Expressiveness: Defining path costs as a composition of functions ($f_n \circ f_{n-1} \circ \dots \circ f_1(x)$) allows the model to capture complex, non-intuitive behaviors in traffic and finance.
Conclusion and Future Directions
While this framework provides a robust theoretical foundation for parametric paths, it currently assumes deterministic weight functions. Future work could extend these models to stochastic environments where costs are probabilistic. Additionally, moving from single-path optimization to multi-path "flows" presents a significant open challenge. Finally, the practical implementation of these algorithms must consider bit complexity, as the numerical representation of composed functions can grow significantly over long paths.
Summary updated