Incremental Topological Ordering and Cycle Detection with Predictions
CoRR(2024)
摘要
This paper leverages the framework of algorithms-with-predictions to design
data structures for two fundamental dynamic graph problems: incremental
topological ordering and cycle detection. In these problems, the input is a
directed graph on n nodes, and the m edges arrive one by one. The data
structure must maintain a topological ordering of the vertices at all times and
detect if the newly inserted edge creates a cycle. The theoretically best
worst-case algorithms for these problems have high update cost (polynomial in
n and m). In practice, greedy heuristics (that recompute the solution from
scratch each time) perform well but can have high update cost in the worst
case.
In this paper, we bridge this gap by leveraging predictions to design a
learned new data structure for the problems. Our data structure guarantees
consistency, robustness, and smoothness with respect to predictions – that is,
it has the best possible running time under perfect predictions, never performs
worse than the best-known worst-case methods, and its running time degrades
smoothly with the prediction error. Moreover, we demonstrate empirically that
predictions, learned from a very small training dataset, are sufficient to
provide significant speed-ups on real datasets.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要