Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

DOI10.1016/J.JCSS.2006.02.001MaRDI QIDQ856420zbMATH OpenOpenAlexWikidataFDO

Authors Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke

Publication date 7 December 2006

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2006.02.001

zbMATH Keywords

graph algorithmfixed-parameter tractabilitygraph modification problemiterative compressionfeedback set problem

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Data Structures
• Parameterized and Exact Computation
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 5158512 (Why is no real title available?)
• scientific article; zbMATH DE number 5158513 (Why is no real title available?)
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1979503 (Why is no real title available?)
• scientific article; zbMATH DE number 1467487 (Why is no real title available?)
• scientific article; zbMATH DE number 2090012 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Algorithm Theory - SWAT 2004
• Algorithms and Data Structures
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Computing and Combinatorics
• Experimental and Efficient Algorithms
• Finding odd cycle transversals.
• Fixed-parameter tractability results for feedback set problems in tournaments
• Graph-Theoretic Concepts in Computer Science
• Introduction to algorithms
• Mathematical Foundations of Computer Science 2004
• ON DISJOINT CYCLES
• On enumerating all minimal solutions of feedback problems
• On the power of unique 2-prover 1-round games
• Optimization, approximation, and complexity classes
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterized and Exact Computation
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• The approximation of maximum subgraph problems
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(64)

• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized algorithm for subset feedback vertex set in tournaments
• Generalized pseudoforest deletion: algorithms and uniform kernel
• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• A Linear Kernel for Planar Feedback Vertex Set
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On polynomial kernels for structural parameterizations of odd cycle transversal
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• An improved FPT algorithm for independent feedback vertex set
• What's next? Future directions in parameterized complexity
• Improved algorithms for feedback vertex set problems
• Parameterized complexity of finding regular induced subgraphs
• A note on the parameterized complexity of unordered maximum tree orientation
• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• Theoretical Computer Science
• An improved FPT algorithm for almost forest deletion problem
• On the Complexity of Singly Connected Vertex Deletion
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• The complexity of König subgraph problems and above-guarantee vertex cover
• Slightly superexponential parameterized problems
• Algorithms and Data Structures
• A quartic kernel for pathwidth-one vertex deletion
• FPT algorithms for connected feedback vertex set
• Mim-width. II. The feedback vertex set problem
• An improved parameterized algorithm for the independent feedback vertex set problem
• A survey of parameterized algorithms and the complexity of edge modification
• Chordal deletion is fixed-parameter tractable
• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
• An FPT algorithm for the vertex cover \(P_4\) problem
• Confronting intractability via parameters
• An improved exact algorithm for undirected feedback vertex set
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• Fixed-parameter enumerability of cluster editing and related problems
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Odd cycle transversal in mixed graphs
• Separator-based data reduction for signed graph balancing
• On the complexity of singly connected vertex deletion
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• Minimization and parameterized variants of vertex partition problems on graphs
• On feedback vertex set: new measure and new structures
• scientific article; zbMATH DE number 7278081 (Why is no real title available?)
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Iterative Compression and Exact Algorithms
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• scientific article; zbMATH DE number 7561552 (Why is no real title available?)
• A polynomial kernel for block graph deletion
• Circumventing connectivity for kernelization
• Vertex cover problem parameterized above and below tight bounds
• Faster deterministic \textsc{Feedback Vertex Set}
• Edge bipartization faster than \(2^k\)
• Fixed-parameter tractability results for feedback set problems in tournaments
• Iterative compression and exact algorithms
• When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices
• Faster graph bipartization
• scientific article; zbMATH DE number 7651211 (Why is no real title available?)
• FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

This page was built for publication: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

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