Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$

DOI10.1007/11847250_17zbMath1154.05327OpenAlexW2283515028MaRDI QIDQ3499736

Serge Gaspers, Fedor V. Fomin, Artem V. Pyatkin

Publication date: 3 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11847250_17

zbMATH Keywords

exact exponential algorithmmaximum induced forestminimum feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

MIP formulations for induced graph optimization problems: a tutorial ⋮ A Moderately Exponential Time Algorithm for Full Degree Spanning Tree ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Robust networked multiagent optimization: designing agents to repair their own utility functions ⋮ Extremal properties of the bipartite vertex frustration of graphs ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Improved algorithms for feedback vertex set problems ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

This page was built for publication: Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$