J. Bang-jensen et A. Yeo, The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs, J ALGORITHM, 41(1), 2001, pp. 1-19
We consider the problem (minimum spanning strong subdigraph (MSSS)) of find
ing the minimum number of arcs in a spanning strongly connected subdigraph
of a strongly connected digraph. This problem is NP-hard for general digrap
hs since it generalizes the Hamiltonian cycle problem. We characterize the
number of arcs in a minimum spanning strong subdigraph for digraphs which a
re either extended semicomplete or semicomplete bipartite. Our proofs lead
to polynomial algorithms for finding an optimal subdigraph for every digrap
h from each of these classes. Our proofs are based on a number of results (
some of which are new and interesting in their own right) on the structure
of cycles and paths in these graphs. Recently, it was shown that the Hamilt
onian cycle problem is polynomially solvable for semicomplete multipartite
digraphs, a superclass of the two classes above [15]. We conjecture that th
e MSSS problem is also polynomial for this class of digraphs. (C) 2001 Acad
emic Press.