Dublois, Louis ;
Hanaka, Tesshu ;
Khosravian Ghadikolaei, Mehdi ;
Lampis, Michael ;
Melissinos, Nikolaos
(In)approximability of Maximum Minimal FVS
Abstract
We study the approximability of the NPcomplete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more wellstudied 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 nontrivial polynomial time approximation for Max Min FVS with a ratio of O(n^{2/3}), as well as a matching hardness of approximation bound of n^{2/3ε}, improving the previous known hardness of n^{1/2ε}. Along the way, we also obtain an O(Δ)approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NPhard from Δ ≥ 9 to Δ ≥ 6.
Having settled the problem’s approximability in polynomial time, we move to the context of superpolynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r, produces an rapproximate solution in time n^O(n/r^{3/2}). This timeapproximation tradeoff is essentially tight: we show that under the ETH, for any ratio r and ε > 0, no algorithm can rapproximate this problem in time n^{O((n/r^{3/2})^{1ε})}, hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and subexponential time, up to an arbitrarily small constant in the second exponent.
BibTeX  Entry
@InProceedings{dublois_et_al:LIPIcs:2020:13347,
author = {Louis Dublois and Tesshu Hanaka and Mehdi Khosravian Ghadikolaei and Michael Lampis and Nikolaos Melissinos},
title = {{(In)approximability of Maximum Minimal FVS}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {3:13:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13347},
URN = {urn:nbn:de:0030drops133477},
doi = {10.4230/LIPIcs.ISAAC.2020.3},
annote = {Keywords: Approximation Algorithms, ETH, Inapproximability}
}
04.12.2020
Keywords: 

Approximation Algorithms, ETH, Inapproximability 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 