Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs

DOI10.1002/JGT.23072arXiv2302.06177OpenAlexW4390543343MaRDI QIDQ6201032FDOQ6201032

Authors: Jørgen Bang-Jensen 

Publication date: 25 March 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: An out-branching $B_u^{+}$ (in-branching $B_u^{-}$) in a digraph $D$ is a connected spanning subdigraph of $D$ in which every vertex except the vertex $u$, called the root, has in-degree (out-degree) one. It is well-known that there exists a polynomial algorithm for deciding whether a given digraph has $k$ arc-disjoint out-branchings with prescribed roots ($k$ is part of the input). In sharp contrast to this, it is already NP-complete to decide if a digraph has one out-branching which is arc-disjoint from some in-branching. A digraph is {�f semicomplete} if it has no pair of non adjacent vertices. A {�f tournament} is a semicomplete digraph without directed cycles of length 2. In this paper we give a complete classification of semicomplete digraphs which have an out-branching $B_u^{+}$ which is arc-disjoint from some in-branching $B_v^{-}$ where $u,v$ are prescribed vertices of $D$. Our characterization, which is surprisingly simple, generalizes a complicated characterization for tournaments from 1991 by the first author and our proof implies the existence of a polynomial algorithm for checking whether a given semicomplete digraph has such a pair of branchings for prescribed vertices $u,v$ and construct a solution if one exists. This confirms a conjecture of Bang-Jensen for the case of semicomplete digraphs.

Full work available at URL: https://arxiv.org/abs/2302.06177

Recommendations

• Modeling, estimation, and their applications for distributed parameter systems
• scientific article; zbMATH DE number 3453478
• One More Proof of Kronecker's Theorem
• A note on power residues
• Generalized Cells in Generalized Manifolds
• scientific article; zbMATH DE number 3183246
• scientific article; zbMATH DE number 3128524
• scientific article; zbMATH DE number 3799115

zbMATH Keywords

polynomial algorithmsemicomplete digrapharc-disjoint subdigraphsout-branchingsin-branchings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Cites Work

• Digraphs
• Title not available (Why is that?)
• Quasi‐transitive digraphs
• On two minimax theorems in graph
• Title not available (Why is that?)
• Edge-disjoint in- and out-branchings in tournaments and related path problems
• Decomposing \(k\)-arc-strong tournaments into strong spanning subdigraphs
• Small degree out‐branchings
• A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph
• Arc-disjoint strong spanning subdigraphs of semicomplete compositions
• Arc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
• Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2

Cited In (1)

• Arc-disjoint out- and in-branchings in compositions of digraphs

This page was built for publication: Arc‐disjoint out‐branchings and in‐branchings in semicomplete digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201032)