Approximation and FPT algorithms for finding DM-irreducible spanning subgraphs

Finding a minimum-weight strongly connected spanning subgraph of an edge-weighted directed graph is one of the most fundamental network design problems. This problem is NP-hard, and a simple 2-approximation algorithm was proposed by Frederickson and Jájá (1981); surprisingly, it still achieves the best known approximation ratio in general. Also, Bang-Jensen and Yeo (2008) showed that the unweighted problem is FPT (fixed-parameter tractable) parameterized by the difference from a trivial upper bound of the optimal value. In this paper, we consider a generalization related to the Dulmage–Mendelsohn decomposition of a bipartite graph, and extend these approximation and FPT results to the generalized setting.