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₁ and A₂ such that both of the spanning subdigraphs D₁=(V,A₁) and D₂=(V,A₂) are strong. Let T be a digraph with t vertices u₁.....,u_t and let H₁....,H_t be digraphs such that H_i has vertices u_i,j,. 1≤J_i≤n_i Then the composition Q=T[H₁...,H_i] is a digraph with vertex set (Formula presented.) and arc set (Formula presented.) We obtain a characterization of digraph compositions Q=T[H₁...,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₁..,H_t in which T is semicomplete and each (Formula presented.) 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₁..,H_t, with T semicomplete, whenever such a decomposition exists.