Bang-Jensen and Gutin's algorithmic conjecture for good pairs in quasi-transitive digraphs
Bang-Jensen and Gutin's algorithmic conjecture for good pairs in quasi-transitive digraphs
Let be a quasi-transitive digraph, meaning that whenever and are arcs, there is an arc between and . For vertices , a good -pair is a pair of arc-disjoint branchings consisting of an out-branching rooted at and an in-branching rooted at .
Bang-Jensen and Gutin's conjecture. There exists a polynomial algorithm for deciding, given a quasi-transitive digraph and two vertices of , whether has a good -pair.
The conjecture asks for an efficient recognition algorithm extending the known result for good -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.