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

DOI10.1016/J.JCSS.2006.02.001zbMATH Open1119.68134OpenAlexW2157295389WikidataQ56209811 ScholiaQ56209811MaRDI QIDQ856420FDOQ856420

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to algorithms
• Optimization, approximation, and complexity classes
• Finding odd cycle transversals.
• ON DISJOINT CYCLES
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Parameterized and Exact Computation
• Computing and Combinatorics
• On the power of unique 2-prover 1-round games
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Graph-Theoretic Concepts in Computer Science
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Fixed-parameter tractability results for feedback set problems in tournaments
• Parameterized algorithms for feedback set problems and their duals in tournaments
• The approximation of maximum subgraph problems
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Algorithm Theory - SWAT 2004
• Algorithms and Data Structures
• On enumerating all minimal solutions of feedback problems
• Experimental and Efficient Algorithms
• Mathematical Foundations of Computer Science 2004

Cited In (66)

• Finding \(k\)-secluded trees faster
• Finding \(k\)-secluded trees faster
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• A faster FPT algorithm for bipartite contraction
• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized algorithm for subset feedback vertex set in tournaments
• Slightly Superexponential Parameterized Problems
• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• On group feedback vertex set parameterized by the size of the cutset
• A Linear Kernel for Planar Feedback Vertex Set
• What’s Next? Future Directions in Parameterized Complexity
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Title not available (Why is that?)
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• An improved FPT algorithm for independent feedback vertex set
• 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
• On the Complexity of Singly Connected Vertex Deletion
• An improved FPT algorithm for almost forest deletion problem
• Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
• The complexity of König subgraph problems and above-guarantee vertex cover
• FPT algorithms for connected feedback vertex set
• On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
• Mim-width. II. The feedback vertex set problem
• On the parameterized complexity of reconfiguration problems
• A survey of parameterized algorithms and the complexity of edge modification
• An improved parameterized algorithm for the independent feedback vertex set problem
• 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
• An improved exact algorithm for undirected feedback vertex set
• Confronting intractability via parameters
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
• Title not available (Why is that?)
• 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
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
• Odd cycle transversal in mixed graphs
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Minimization and parameterized variants of vertex partition problems on graphs
• Separator-based data reduction for signed graph balancing
• On the complexity of singly connected vertex deletion
• On feedback vertex set: new measure and new structures
• 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
• A polynomial kernel for block graph deletion
• Circumventing connectivity for kernelization
• Title not available (Why is that?)
• Faster deterministic \textsc{Feedback Vertex Set}
• Vertex cover problem parameterized above and below tight bounds
• Title not available (Why is that?)
• Edge bipartization faster than \(2^k\)
• Title not available (Why is that?)
• Fixed-parameter tractability results for feedback set problems in tournaments
• Iterative compression and exact algorithms
• Faster graph bipartization
• 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
• Contracting graphs to paths and trees

   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 👍 👎

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)