2026-07-23T13:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13347 2024-03-06T10:51:45Z ddc:004 open_access

(In)approximability of Maximum Minimal FVS Dublois, Louis Hanaka, Tesshu Khosravian Ghadikolaei, Mehdi Lampis, Michael Melissinos, Nikolaos Approximation Algorithms ETH Inapproximability 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 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 NP-hard from Δ ≥ 9 to Δ ≥ 6. 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: we show that under the ETH, for any ratio r and ε > 0, no algorithm can r-approximate 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 sub-exponential time, up to an arbitrarily small constant in the second exponent. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louis Dublois and Tesshu Hanaka and Mehdi Khosravian Ghadikolaei and Michael Lampis and Nikolaos Melissinos 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.3 urn:nbn:de:0030-drops-133477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.3 eng https://creativecommons.org/licenses/by/3.0/legalcode