An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
From MaRDI portal
Publication:2464330
DOI10.1007/s00224-007-1345-zzbMath1148.68037OpenAlexW1971393213WikidataQ57359936 ScholiaQ57359936MaRDI QIDQ2464330
Michael R. Fellows, Frank Dehne, Michael A. Langston, Kim Stevens, Frances A. Rosamond
Publication date: 19 December 2007
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-007-1345-z
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
On the Complexity of Singly Connected Vertex Deletion, What’s Next? Future Directions in Parameterized Complexity, A polynomial kernel for block graph deletion, MIP formulations for induced graph optimization problems: a tutorial, Contracting graphs to paths and trees, A faster FPT algorithm for bipartite contraction, Confronting intractability via parameters, On feedback vertex set: new measure and new structures, Improved FPT Algorithms for Deletion to Forest-Like Structures., Chordal deletion is fixed-parameter tractable, Slightly Superexponential Parameterized Problems, Fixed-parameter tractability results for feedback set problems in tournaments, Faster deterministic \textsc{Feedback Vertex Set}, Iterative compression and exact algorithms, A Quartic Kernel for Pathwidth-One Vertex Deletion, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, Parameterized complexity of finding regular induced subgraphs, Unnamed Item, On the complexity of singly connected vertex deletion, On group feedback vertex set parameterized by the size of the cutset
