(In)approximability of maximum minimal FVS

DOI10.1016/J.JCSS.2021.09.001MaRDI QIDQ2051849zbMATH OpenOpenAlexFDO

Authors Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, Nikolaos Melissinos

Publication date 25 November 2021

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.09971, https://drops.dagstuhl.de/opus/volltexte/2020/13347/

zbMATH Keywords

approximation algorithmsETHinapproximability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: We study the approximability of the NP-complete extsc{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: extsc{Maximum Minimal Vertex Cover}, for which the best achievable approximation ratio is $sqrtn$, and extsc{Upper Dominating Set}, which does not admit any $n^{1-epsilon}$ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for extsc{Max Min FVS} with a ratio of $O(n^{2/3})$, as well as a matching hardness of approximation bound of $n^{2/3-epsilon}$, improving the previous known hardness of $n^{1/2-epsilon}$. The approximation algorithm also gives a cubic kernel when parameterized by the solution size. Along the way, we also obtain an $O(Delta)$-approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from $Deltage9$ to $Deltage6$. 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 $epsilon>0$, no algorithm can $r$-approximate this problem in time $n^{O((n/r^{3/2}{)}^{1-epsilon})}$, 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.

Recommendations

• In)approximability of Maximum Minimal FVS
• scientific article; zbMATH DE number 895368
• Approximating a generalization of MAX 2SAT and MIN 2SAT
• The Parameterized Complexity of Maximality and Minimality Problems
• The parameterized complexity of maximality and minimality problems
• Fixed-parameter Approximability of Boolean MinCSPs
• On approximation algorithms for the minimum satisfiability problem

Cites work

• A note on the approximation of a minimum-weight maximal independent set
• Algorithmic aspects of upper paired-domination in graphs
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• An improved algorithm for parameterized edge dominating set problem
• An induced subgraph characterization of domination perfect graphs
• Approximating MAX SAT by moderately exponential and parameterized algorithms
• Approximation of min coloring by moderately exponential algorithms
• Bounds on upper transversals in hypergraphs
• Chordal graphs and upper irredundance, upper domination and independence
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Exact and approximate bandwidth
• Exponential-time approximation of weighted set cover
• Grundy distinguishes treewidth from pathwidth
• scientific article; zbMATH DE number 7650943 (Why is no real title available?)
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• Improved (In-)approximability bounds for \(d\)-scattered set
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum minimal vertex cover parameterized by vertex cover
• New tools and connections for exponential-time approximation
• On the complexity of the upper r-tolerant edge cover problem
• On the computational complexity of upper fractional domination
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• On the max min vertex cover problem
• On the maximum weight minimal separator
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• On upper transversals in 3-uniform hypergraphs
• Parameterized algorithms
• Parameterized algorithms for even cycle transversal
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sub-exponential approximation schemes for CSPs: from dense to almost sparse
• The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design
• The lazy bureaucrat scheduling problem
• The many facets of upper domination
• Time-approximation trade-offs for inapproximable problems
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Upper domination: towards a dichotomy through boundary properties
• Upper transversals in hypergraphs
• Weighted upper domination number
• Weighted upper edge cover: complexity and approximability

Cited in

(6)

• Time-approximation trade-offs for inapproximable problems
• Time-approximation trade-offs for inapproximable problems
• Minimum maximal acyclic matching in proper interval graphs
• On the complexity of minimum maximal acyclic matchings
• Upper Clique Transversals in Graphs
• Parameterized max min feedback vertex set

This page was built for publication: (In)approximability of maximum minimal FVS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2051849)