
(In)approximability of maximum minimal FVS
Dublois, Louis; Hanaka, Tesshu; Khosravian Ghadikolaei, Mehdi; Lampis, Michael; Melissinos, Nikolaos (2020), (In)approximability of maximum minimal FVS, Journal of Computer and System Sciences, 124, p. 26-40. 10.1016/j.jcss.2021.09.001
View/ Open
Type
Article accepté pour publication ou publiéDate
2020Journal name
Journal of Computer and System SciencesVolume
124Publisher
Elsevier
Pages
26-40
Publication identifier
Metadata
Show full item recordAuthor(s)
Dublois, LouisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Hanaka, Tesshu
Khosravian Ghadikolaei, Mehdi
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lampis, Michael
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Melissinos, Nikolaos
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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 , 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 Maximum Minimal Feedback Vertex Set with a ratio of O(n2/3), as well as a matching hardness of approximation bound of n2/3−, improving the previously known hardness of n1/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 nO(n/r3/2). This time-approximation trade-off is essentially tight under the ETH.Subjects / Keywords
Approximation algorithms; ETH; InapproximabilityRelated items
Showing items related by title and author.
-
Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2020) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2019) Communication / Conférence
-
Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris (2022) Article accepté pour publication ou publié
-
Khoshkhah, Kaveh; Khosravian Ghadikolaei, Mehdi; Monnot, Jérôme; Theis, Dirk Oliver (2019) Article accepté pour publication ou publié
-
Belmonte, Rémy; Khosravian Ghadikolaei, Mehdi; Kiyomi, Masashi; Lampis, Michael; Otachi, Yota (2019) Article accepté pour publication ou publié