Parameterized max min feedback vertex set

DOI10.1137/23M1605247MaRDI QIDQ6939693zbMATH OpenFDO

Authors Michael Lampis, Nikolaos Melissinos, Manolis Vasilakis

Publication date 21 August 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1605247

zbMATH Keywords

ETHfeedback vertex setparameterized algorithmstreewidth

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• (In)approximability of maximum minimal FVS
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Computing the largest bond and the maximum connected cut of a graph
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Digraph coloring and distance to acyclicity
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Graph theory
• Grundy Distinguishes Treewidth from Pathwidth
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• Maximum minimal vertex cover parameterized by vertex cover
• Minimum maximal acyclic matching in proper interval graphs
• On directed feedback vertex set parameterized by treewidth
• On the complexity of solution extension of optimization problems
• On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
• On the max min vertex cover problem
• Parameterized algorithms
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• Parameterized max min feedback vertex set
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Slightly superexponential parameterized problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design
• The many facets of upper domination
• The three-in-a-tree problem
• Three-in-a-tree in near linear time
• 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
• Which problems have strongly exponential complexity?

This page was built for publication: Parameterized max min feedback vertex set

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