Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search
Tacheny, N. (2026)
In multi-criteria graph traversal, paths are compared via Pareto dominance—an ordering that identifies which paths are non-dominated, but says nothing about which path to expand next or when the search may stop. As a result, existing approaches rely on external mechanisms—heuristics, scalarization, or population-based exploration—while Pareto dominance remains confined to passive roles such as pruning or ranking. This paper shows that, under constrained cost models—finite cost grids, Markovian transitions, and a nonzero progress measure—Pareto geometry alone is sufficient to drive both scheduling and termination.
We show that extracting exclusively from the first Pareto layer—the skyline—induces a deterministic descent in a discrete completion potential, ensuring monotone progress toward solution completion. In parallel, a vector lower-bound certificate provides a stopping condition that guarantees dominance coverage of all remaining traversals, without requiring a predefined number of solutions. The resulting framework operates without scalarization, heuristic guidance, or probabilistic models, and repositions Pareto dominance from a passive filter to a deterministic driver of search.