Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs |
| |
Authors: | Jørgen Bang‐Jensen Jing Huang |
| |
Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE, UNIVERSITY OF SOUTHERN DENMARK, ODENSE, DENMARK;2. DEPARTMENT OF MATHEMATICS AND STATISTICS, UNIVERSITY OF VICTORIA, VICTORIA, CANADA |
| |
Abstract: | 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 ). This problem has been shown to be polynomial time solvable for semicomplete digraphs 2 and for quasi‐transitive digraphs 6 . 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 for semicomplete digraphs and solves an open problem from 4 . |
| |
Keywords: | Locally semicomplete digraph structure of locally semicomplete digraphs arc‐disjoint in‐ and out‐branchings arc‐contraction polynomial time algorithm |
|
|