文章基本信息

标题：(In)approximability of Maximum Minimal FVS
本地全文：下载
作者：Louis Dublois ; Tesshu Hanaka ; Mehdi Khosravian Ghadikolaei 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：181
页码：1-14
DOI：10.4230/LIPIcs.ISAAC.2020.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â^Sn, 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.
关键词：Approximation Algorithms; ETH; Inapproximability