Two spanning temporal arborescences under half-connectivity

Let N=((Vs,A),τ)N=((V\cup s,A),\tau) be an acyclic temporal network on n4n\ge 4 vertices. For vertices s,vV{s}s,v\in V\cup\{s\}, let λN(s,v)\lambda_N(s,v) denote the maximum number of arc-disjoint τ\tau-respecting (s,v)(s,v)-paths, and let a spanning τ\tau-respecting ss-arborescence be a spanning arborescence rooted at ss whose root-to-vertex paths respect the temporal ordering.

Two-arborescence conjecture. If

λN(s,v)n2\lambda_N(s,v)\ge \frac n2

for every vVv\in V, then NN contains a packing of 22 spanning τ\tau-respecting ss-arborescences.

This would improve the preceding sufficient condition λN(s,v)n1\lambda_N(s,v)\ge n-1 for packing two spanning temporal arborescences. The conjecture is presented as an open strengthening for acyclic temporal networks; no resolution is given here.

Sources & referencesView supporting material

Primary source

Romain Chapoullié and Zoltán Szigeti, “On packing time-respecting arborescences”, arXiv:2203.01096 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.