Feasible indexing conjecture for successor and ancestor sets of weakly connected DAGs
Feasible indexing conjecture for successor and ancestor sets of weakly connected DAGs
Let be a weakly connected directed acyclic graph with nodes, and let an indexing assign the nodes the labels . For each node , let be its successor set and let be its ancestor set:
Let and denote the associated lexicographic orders, and suppose the indexing satisfies the paper's constraint for all .
Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,
This strengthens the successor-set ordering to break ties using ancestor sets. The paper reports numerical verification for every weakly connected DAG with at most nodes, but gives no general construction of a feasible indexing; the conjecture remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Shiqiang Zhang and Ruth Misener, “Beyond adjacency: Graph encoding with reachability and shortest paths”, arXiv:2509.20247 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.