Premium
Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs
Author(s) -
BangJensen Jørgen,
Huang Jing
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21786
Subject(s) - digraph , mathematics , combinatorics , disjoint sets , vertex (graph theory) , constructive , mathematical proof , arc (geometry) , transitive relation , discrete mathematics , graph , computer science , geometry , process (computing) , operating system
Deciding whether a digraph contains a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex is a well‐known NP‐complete problem (as proved by Thomassen, see [2][J. Bang‐Jensen, 1991]). This problem has been shown to be polynomial time solvable for semicomplete digraphs [2][J. Bang‐Jensen, 1991] and for quasi‐transitive digraphs [6][J. Bang‐Jensen, 1995]. In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from [2][J. Bang‐Jensen, 1991] for semicomplete digraphs and solves an open problem from [4][J. Bang‐Jensen, 1998].