Back to Search
Start Over
A 4 + ϵ approximation for k-connected subgraphs.
- Source :
-
Journal of Computer & System Sciences . Feb2022, Vol. 123, p64-75. 12p. - Publication Year :
- 2022
-
Abstract
- We obtain approximation ratio 4 + 2 ℓ ≈ 4 + 4 lg k lg n − lg k for the (undirected) k -Connected Subgraph problem, where ℓ = ⌊ lg n − lg k + 1 2 lg k + 1 ⌋ is the largest integer such that 2 ℓ − 1 k 2 ℓ + 1 ≤ n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n ≥ k 3 (the case ℓ = 1). Our result implies an fpt-approximation ratio 4 + ϵ that matches (up to the "+ ϵ " term) the best known ratio 4 for k = 6 , 7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*INTEGERS
*UNDIRECTED graphs
*APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 123
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 152816052
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.07.006