Bang-Jensen and Gutin's algorithmic conjecture for good pairs in quasi-transitive digraphs

Let D=(V,A)D=(V,A) be a quasi-transitive digraph, meaning that whenever uvuv and vwvw are arcs, there is an arc between uu and ww. For vertices u,vVu,v\in V, a good (u,v)(u,v)-pair is a pair of arc-disjoint branchings consisting of an out-branching rooted at uu and an in-branching rooted at vv.

Bang-Jensen and Gutin's conjecture. There exists a polynomial algorithm for deciding, given a quasi-transitive digraph D=(V,A)D=(V,A) and two vertices u,vu,v of VV, whether DD has a good (u,v)(u,v)-pair.

The conjecture asks for an efficient recognition algorithm extending the known result for good (u,u)(u,u)-pairs in quasi-transitive digraphs. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Joergen Bang-Jensen and Yun Wang, “Arc-disjoint out- and in-branchings in compositions of digraphs”, arXiv:2302.08283 (2023).

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.