TY - GEN

T1 - (In)approximability of maximum minimal FVS

AU - Dublois, Louis

AU - Hanaka, Tesshu

AU - Ghadikolaei, Mehdi Khosravian

AU - Lampis, Michael

AU - Melissinos, Nikolaos

N1 - Funding Information:
Funding This work is partially supported by PRC CNRS JSPS project PARAGA and by JSPS KAKENHI Grant Number JP19K21537.
Publisher Copyright:
© Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos.

PY - 2020/12

Y1 - 2020/12

N2 - 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 n1−∊ 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(n2/3), as well as a matching hardness of approximation bound of n2/3−∊, improving the previous known hardness of n1/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 nO(n/r3/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 nO((n/r3/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.

AB - 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 n1−∊ 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(n2/3), as well as a matching hardness of approximation bound of n2/3−∊, improving the previous known hardness of n1/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 nO(n/r3/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 nO((n/r3/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.

UR - http://www.scopus.com/inward/record.url?scp=85100950255&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100950255&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2020.3

DO - 10.4230/LIPIcs.ISAAC.2020.3

M3 - Conference contribution

AN - SCOPUS:85100950255

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 31

EP - 314

BT - 31st International Symposium on Algorithms and Computation, ISAAC 2020

A2 - Cao, Yixin

A2 - Cheng, Siu-Wing

A2 - Li, Minming

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st International Symposium on Algorithms and Computation, ISAAC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -