Arc-disjoint strong spanning subdigraphs of semicomplete compositions

A strong arc decomposition of a digraph (Formula presented.) is a decomposition of its arc set (Formula presented.) into two disjoint subsets (Formula presented.) and (Formula presented.) such that both of the spanning subdigraphs (Formula presented.) and (Formula presented.) are strong. Let (Formula presented.) be a digraph with (Formula presented.) vertices (Formula presented.) and let (Formula presented.) be digraphs such that (Formula presented.) has vertices (Formula presented.). Then the composition (Formula presented.) is a digraph with vertex set (Formula presented.) and arc set (Formula presented.) We obtain a characterization of digraph compositions (Formula presented.) which have a strong arc decomposition when (Formula presented.) is a semicomplete digraph and each (Formula presented.) 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 (Formula presented.) in which (Formula presented.) 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 (Formula presented.), with (Formula presented.) semicomplete, whenever such a decomposition exists.