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

DOI10.1007/11847250_17zbMath1154.05327MaRDI 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 algorithm; maximum induced forest; minimum feedback vertex set

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs, Unnamed Item, MIP formulations for induced graph optimization problems: a tutorial, Robust networked multiagent optimization: designing agents to repair their own utility functions, Extremal properties of the bipartite vertex frustration of graphs, 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, An improved FPT algorithm for almost forest deletion problem, Fixed-parameter tractability for subset feedback set problems with parity constraints, A Moderately Exponential Time Algorithm for Full Degree Spanning Tree, A Linear Kernel for Planar Feedback Vertex Set, Iterative Compression for Exactly Solving NP-Hard Minimization Problems