License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2020.3
URN: urn:nbn:de:0030-drops-133477
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13347/
 Go to the corresponding LIPIcs Volume Portal

### (In)approximability of Maximum Minimal FVS

 pdf-format:

### Abstract

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.

### BibTeX - Entry

```@InProceedings{dublois_et_al:LIPIcs:2020:13347,
author =	{Louis Dublois and Tesshu Hanaka and Mehdi Khosravian Ghadikolaei and Michael Lampis and Nikolaos Melissinos},
title =	{{(In)approximability of Maximum Minimal FVS}},
booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages =	{3:1--3:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-173-3},
ISSN =	{1868-8969},
year =	{2020},
volume =	{181},
editor =	{Yixin Cao and Siu-Wing Cheng and Minming Li},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy
{"ft_lang_label":"__label__en","ft_lang_prob":0.8035666,"math_prob":0.8474549,"size":2784,"snap":"2022-05-2022-21","text_gpt3_token_len":763,"char_repetition_ratio":0.1320144,"word_repetition_ratio":0.015957447,"special_character_ratio":0.26329023,"punctuation_ratio":0.15234375,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95959914,"pos_list":[0,1,2,3,4,5,6],"im_url_duplicate_count":[null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-05-20T22:41:27Z\",\"WARC-Record-ID\":\"<urn:uuid:71b242d5-d17f-44e0-8e16-3cb60c579946>\",\"Content-Length\":\"7134\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6ec26b98-72a4-4d76-ba5b-21d65802d12b>\",\"WARC-Concurrent-To\":\"<urn:uuid:86844237-cb3b-40c0-b083-b0d2b9fbe21d>\",\"WARC-IP-Address\":\"192.76.146.6\",\"WARC-Target-URI\":\"https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=13347\",\"WARC-Payload-Digest\":\"sha1:SHVPD5NBFKDYHRWNQXU2CRAJXBSDDCYF\",\"WARC-Block-Digest\":\"sha1:6UDIXZ6ODVZVFEBICAQ3JIKP7BJGR3YC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-21/CC-MAIN-2022-21_segments_1652662534693.28_warc_CC-MAIN-20220520223029-20220521013029-00532.warc.gz\"}"}