Arc‐disjoint strong spanning subdigraphs of semicomplete compositions

A strong arc decomposition of a digraph D = ( V , A ) is a decomposition of its arc set A into two disjoint subsets A 1 and A 2 such that both of the spanning subdigraphs D 1 = ( V , A 1 ) and D 2 = ( V , A 2 ) are strong. Let T be a digraph with t vertices u 1 , … , u t and let H 1 , … , H t be digraphs such that H i has vertices u i , j i, 1 ≤ j i ≤ n i . Then the composition Q = T [ H 1 , … , H t ] is a digraph with vertex set ⋃ i = 1 t V ( H i ) = { u i , j i∣ 1 ≤ i ≤ t , 1 ≤ j i ≤ n i } and arc set⋃ i = 1 t A ( H i )⋃⋃ u i u p ∈ A ( T ){ u i j iu p q p∣ 1 ≤ j i ≤ n i , 1 ≤ q p ≤ n p }. We obtain a characterization of digraph compositions Q = T [ H 1 , … , H t ] which have a strong arc decomposition when T is a semicomplete digraph and each H i is an arbitrary digraph. Our characterization generalizes a characterization by Bang‐Jensen and Yeo (2003) of semicomplete digraphs with a strong arc decomposition and solves an open problem by Sun, Gutin, and Ai (2019) on strong arc decompositions of digraph compositions Q = T [ H 1 , … , H t ] in which T is semicomplete and each H i is arbitrary. Our proofs are constructive and imply the existence of a polynomial algorithm for constructing a strong arc decomposition of a digraph Q = T [ H 1 , … , H t ] , with T semicomplete, whenever such a decomposition exists.