Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916398605795328 |
|---|---|
| author | Norose, Ryoma Yamaguchi, Yutaro |
| author_facet | Norose, Ryoma Yamaguchi, Yutaro |
| contents | 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á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 decompositions of bipartite graphs instead of the strong connectivity of directed graphs, and extend these approximation and FPT results to the generalized setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17927 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs Norose, Ryoma Yamaguchi, Yutaro Data Structures and Algorithms Combinatorics 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á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 decompositions of bipartite graphs instead of the strong connectivity of directed graphs, and extend these approximation and FPT results to the generalized setting. |
| title | Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2404.17927 |