Generalized parametric path problems

Kshitij Gajjar, Girish Varma, Prerona Chatterjee, Jaikumar RadhakrishnanUAI 2021

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.

Illustration of time-dependent paths where the FIFO property may not hold, showing non-monotonic arrival times.

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.

Algorithm 1 for solving GPP with linear weight functions by tracking both upper and lower cost envelopes.

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

BibTeX
@inproceedings{gajjar2021generalized,
  author = {Kshitij Gajjar and Girish Varma and Prerona Chatterjee and Jaikumar Radhakrishnan},
  title = {{Generalized parametric path problems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2021},
}
Figure