# Skyline-First Traversal as a Control Mechanism for Multi-Criteria Graph Search

arXiv: https://arxiv.org/abs/2604.19807 · HTML: https://mlsanity.com/paper/2604.19807/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 7 references that are in the map.
- First posted on arXiv 14 Apr 2026.

## Builds on (most cited first, 1 of 1)

- [Parametric Traversal for Multi-Dimensional Cost-Aware Graph Reasoning](https://mlsanity.com/paper/2602.13369/) (2026)

## Abstract (arXiv)

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. Our analysis establishes deterministic potential descent, certified termination via dominance coverage, a uniform bound on layer width induced by cost-grid geometry, and greedy cost-space dispersion within the skyline. 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.