Back to Search
Start Over
(In)approximability of maximum minimal FVS.
- Source :
-
Journal of Computer & System Sciences . Mar2022, Vol. 124, p26-40. 15p. - Publication Year :
- 2022
-
Abstract
- We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover , for which the best achievable approximation ratio is n , and Upper Dominating Set , which does not admit any n 1 − ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O (n 2 / 3) , as well as a matching hardness of approximation bound of n 2 / 3 − ϵ , improving the previously known hardness of n 1 / 2 − ϵ. Having settled the problem's approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r , produces an r -approximate solution in time n O (n / r 3 / 2). This time-approximation trade-off is essentially tight under the ETH. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 124
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 153707977
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.09.001