The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Mathematics and Computer Science, Odense University^{3} BRICS, Department of Computer Science, Aarhus University

Abstract:

We consider the problem (minimum spanning strong subdigraph (MSSS)) of finding the minimum number of arcs in a spanning strongly connected subdigraph of a strongly connected digraph. This problem is NP-hard for general digraphs since it generalizes the Hamiltonian cycle problem. We characterize the number of arcs in a minimum spanning strong subdigraph for digraphs which are either extended semicomplete or semicomplete bipartite. Our proofs lead to polynomial algorithms for finding an optimal subdigraph for every digraph 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 Hamiltonian cycle problem is polynomially solvable for semicomplete multipartite digraphs, a superclass of the two classes above [[15]]. We conjecture that the MSSS problem is also polynomial for this class of digraphs. [15] J. Bang-Jensen, G. Gutin and A. Yeo, A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs. J. Graph Theory 29 (1998), pp. 111–132. MathSciNet

Type:

Journal article

Language:

English

Published in:

Journal of Algorithms, 2001, Vol 41, Issue 1, p. 1-19