Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs

Finding a minimum strongly connected spanning subgraph of a given directed graph generalizes the well-known strong connectivity augmentation problem, and it is NP-hard. For the weighted problem, a simple 2-approximation algorithm was proposed by Frederickson and J\'aj\'a (1981) ; surprisingly, it still achieves the best known approximation ratio in general. Also, the unweighted problem was shown to be FPT by Bang-Jensen and Yeo (2008), where the parameter is the difference from the trivial upper bound of the optimal value. In this paper, we consider a generalized problem related to the Dulmage--Mendelsohn decompositions of bipartite graphs instead of the strong connectivity of directed graphs, and extend the above approximation and FPT results to this setting.