(In)approximability of maximum minimal FVS
(In)approximability of maximum minimal FVS
复制标题
最大最小 FVS 的（In）近似性
DOI：
10.1016/j.jcss.2021.09.001
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Melissinos Nikolaos
中科院分区：
文献类型：
--
作者：
Dublois Louis;Hanaka Tesshu;Khosravian Ghadikolaei Mehdi;Lampis Michael;Melissinos Nikolaos
研究了NP完全最大最小反馈点集问题的可逼近性。非正式地，这个自然问题似乎位于两个更好的研究这类问题之间的中间空间：最大最小顶点覆盖，其最佳可实现的近似比是n，以及上支配集，不允许任何n1 − n近似。我们通过展示最大最小反馈顶点集的第一个非平凡多项式时间近似来确认和量化这种直觉，其比率为O（n 2/3），以及近似界的匹配硬度为n 2/3− n，改进了先前已知的硬度n 1/2− n。在解决了问题在多项式时间内的可逼近性之后，我们转到超多项式时间的上下文中。我们设计了一个概括我们的近似算法，对于任何所需的近似比r，产生一个r-近似解的时间n O（n/r 3/2）。这种时间近似的权衡在ETH下基本上是严格的。
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.