(In)approximability of maximum minimal FVS
From MaRDI portal
Publication:2051849
DOI10.1016/j.jcss.2021.09.001zbMath1478.68448arXiv2009.09971OpenAlexW3201167795MaRDI QIDQ2051849
Louis Dublois, Michael Lampis, Mehdi Khosravian Ghadikolaei, Tesshu Hanaka, 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
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (2)
Minimum maximal acyclic matching in proper interval graphs ⋮ On the complexity of minimum maximal acyclic matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- On the max min vertex cover problem
- Exact and approximate bandwidth
- Upper domination: towards a dichotomy through boundary properties
- On the computational complexity of upper fractional domination
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Chordal graphs and upper irredundance, upper domination and independence
- A note on the approximation of a minimum-weight maximal independent set
- The lazy bureaucrat scheduling problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On upper transversals in 3-uniform hypergraphs
- Time-approximation trade-offs for inapproximable problems
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- The many facets of upper domination
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the complexity of the upper \(r\)-tolerant edge cover problem
- Improved (In-)approximability bounds for \(d\)-scattered set
- New tools and connections for exponential-time approximation
- Algorithmic aspects of upper paired-domination in graphs
- Bounds on upper transversals in hypergraphs
- On the maximum weight minimal separator
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Weighted upper domination number
- Upper transversals in hypergraphs
- On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
- An Improved Algorithm for Parameterized Edge Dominating Set Problem
- The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse
- An induced subgraph characterization of domination perfect graphs
- Parameterized Algorithms for Even Cycle Transversal
- Weighted Upper Edge Cover: Complexity and Approximability
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
This page was built for publication: (In)approximability of maximum minimal FVS
