Decomposing locally semicomplete digraphs into strong spanning subdigraphs

摘要

We prove that the arc set of every 2-arc-strong locally semicomplete digraph D = (V, A) which is not the second power of an even cycle can be partitioned into two sets A_1, A_2 such that both of the spanning subdigraphs D_1 = (V, A_1) and D_2 = (V, A_2) are strongly connected. Moreover, we show that such a partition (if it exists) can be obtained in polynomial time. This generalizes a result from Bang-Jensen and Yeo (2004) [5] on semicomplete digraphs and implies that every 2-arc-strong locally semicomplete digraph D = (V, A) has a pair of arc-disjoint branchings B_u~- B_v~+ such that B_u~- is an in-branching rooted at u and B_v~+ is an out-branching rooted at v where u, v ∈ V can be chosen arbitrarily. This generalizes results from Bang-Jensen (1991) [2] for tournaments and Bang-Jensen and Yeo (2004) [5] for semicomplete digraphs.