Pith. Sign in

REVIEW

An O(n^{2.75}) algorithm for online topological ordering

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Deepak Ajwani, Tobias Friedrich, Ulrich Meyer

Data Structures and Algorithms · Submitted 21 Feb 2006 · 14 references

Pith's verdict: Clever bucket-based algorithm with a plausible amortized bound, but the printed proof of the key lemma is invalid; the result is likely repairable and deserves peer review after a fix.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 3 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDcs/0602073 (version 2)
Pith IDCYR2V4Y4, Pith's permanent record of this paper and its review
CitationDeepak Ajwani, Tobias Friedrich, Ulrich Meyer. "An O(n^{2.75}) algorithm for online topological ordering." arXiv:cs/0602073 (2006). https://pith.science/paper/CYR2V4Y4
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

A bucketed data structure keeps an online topological order in O(n^2.75) worst-case time, improving the previous dense-DAG bound of O(m^1.5 + n^2 log n).

The reading

Imagine a set of tasks with precedence rules: if task A must happen before task B, we write an arrow A to B, and a topological order is a list of the tasks that respects every arrow. Some applications, such as incremental compilers or pointer analysis, add arrows over time and need the list updated quickly without recomputing it from scratch. This paper gives a simple rule for that. When a new arrow points backward in the current list, only the tasks sitting between the two endpoints can be affected. The algorithm collects those tasks, reorders them recursively, and stops as soon as the list is valid again. To keep each step cheap, outgoing and incoming edges of each task are stored in buckets grouped by how far apart the two endpoints are in the current order. Swapping two tasks then touches only a few buckets, and the authors prove that over a whole sequence of edge insertions, the total distance moved by all swapped tasks is at most about n^2.5. Choosing the bucket size to balance collection and update costs yields the O(n^2.75) time bound. The paper also reports C++ experiments showing the method is two to thirty times faster than older algorithms on a constructed hard instance, and within a small constant factor of them on random instances. The algorithm even supports edge deletion, although the runtime guarantee is for insertions only.
Extended reading notes

Core claim

The paper's central claim is: 'We propose a simple algorithm that works in O(n^{2.75} sqrt log n) time and O(n^2) space, thereby improving upon the results of Katriel and Bodlaender for dense DAGs,' with data-structure variants giving O(n^{2.75}) time (Section 5). If true, an online edge-insertion sequence on an n-node DAG can be processed in O(n^{2.75}) worst-case time independent of m, beating the previous best O(min(m^{3/2} log n, m^{3/2}+n^2 log n)).

Load-bearing premise

The runtime bound rests on Lemma 11, which asserts that the total topological distance moved by all swapped node pairs over the entire insertion sequence is O(n^{5/2}). The proof optimizes a linear program over variables X(i,j) representing swap distances indexed by final positions, with the explicitly stated caveat that the constraints are 'necessary but not sufficient' (Section 4, Lemma 11). If the LP omits a real restriction of the swap process, the amortized sum might be larger, and the O(n^{2.75}) exponent would not follow. In fact, the printed dual solution violates nonnegativity, so the lemma is not proven as written.

Original abstract

We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O(min(m^{3/2} log(n), m^{3/2} + n^2 log(n)) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting. Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,652 input tokens, $0.0002 reported.

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.53 · human participants 0.02 · controlled comparison 0.50 · randomized assignment 0.02 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.04.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; .

We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O(min(m^{3/2} log(n), m^{3/2} + n^2 log(n)) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting. Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges m inserted. contribution 0.99 0.96 0.88 asserted 1.00
s1 For dense DAGs, this is an improvement over the previous best result of O(min(m^{3/2} log(n), m^{3/2} + n^2 log(n)) by Katriel and Bodlaender. result 0.60 0.23 0.17 asserted 1.00
s2 We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting. contribution 0.76 0.94 0.05 asserted 0.99
s3 Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs. result 0.99 0.95 0.16 asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.98 · evidence from proof or derivation 0.47.

What was examined, and what was not

sources read
  • arXiv listing abstract v2
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 1. Our algorithm 4
Figure 2. Our hard-case graph For an example with n nodes, we divide the set of nodes into four blocks of dif￾ferent sizes: block 1 consist of nodes [0 . . n/3), block 2 of nodes [n/3 . . n/2), block 3 of nodes [n/2 . . 2n/3), and block 4 of nodes [2n/3 . . n). First, we insert n − 4 edges such that within each block, the vertices form a directed path from left to right. Then we insert the following edges, 15
Figure 3. Experimental data on full random graphs with varying
Figure 4. Experimental data on random graphs with n = 1000 and varying m
Figure 5. Experimental data on a class of hard instances with varyin

Figures reproduced from arXiv:cs/0602073 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.