Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
<|reference_start|>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 equivalent to the weighted version of the well-known strong connectivity augmentation problem. This problem is NP-hard, and 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, 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 decompositions of bipartite graphs instead of the strong connectivity of directed graphs, and extend these approximation and FPT results to the generalized setting.<|reference_end|>
@article{norose2024approximation,
    title={Approximation and FPT Algorithms for Finding DM-Irreducible Spanning
  Subgraphs},
    author={Ryoma Norose and Yutaro Yamaguchi},
    journal={arXiv preprint arXiv:2404.17927},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.17927},
    primaryClass={cs.DS math.CO}
}