Feasible indexing conjecture for successor and ancestor sets of weakly connected DAGs

From papers

Let G=(V,E)G=(V,E) be a weakly connected directed acyclic graph with nn nodes, and let an indexing assign the nodes the labels 1,,n1,\ldots,n. For each node vv, let S(v)\mathcal S(v) be its successor set and let A(v)\mathcal A(v) be its ancestor set:

A(v)=uV\vnode u can reach node v.\mathcal A(v)=\\{u\in V\backslash\\{v\\}\mid \text{node }u\text{ can reach node }v\\}.

Let LO(S(v))LO(\mathcal S(v)) and LO(A(v))LO(\mathcal A(v)) denote the associated lexicographic orders, and suppose the indexing satisfies the paper's constraint LO(S(v))LO(S(v+1))LO(\mathcal S(v))\le LO(\mathcal S(v+1)) for all v[n1]v\in[n-1].

Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,

LO(S(v))=LO(S(v+1))LO(A(v))LO(A(v+1)),v[n1].LO(\mathcal S(v))=LO(\mathcal S(v+1))\Rightarrow LO(\mathcal A(v))\le LO(\mathcal A(v+1)),\qquad \forall v\in[n-1].

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 77 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

No solutions have been posted yet.