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

DOI10.1016/j.jcss.2006.02.001zbMath1119.68134OpenAlexW2157295389WikidataQ56209811 ScholiaQ56209811MaRDI QIDQ856420

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

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

A parameterized complexity view on collapsing \(k\)-cores, On the Complexity of Singly Connected Vertex Deletion, On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, An improved deterministic parameterized algorithm for cactus vertex deletion, Unnamed Item, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, What’s Next? Future Directions in Parameterized Complexity, Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\), A polynomial kernel for block graph deletion, Odd cycle transversal in mixed graphs, Separator-based data reduction for signed graph balancing, Finding \(k\)-secluded trees faster, Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel, A parameterized algorithm for subset feedback vertex set in tournaments, A Linear Kernel for Planar Feedback Vertex Set, Finding \(k\)-secluded trees faster, A survey of parameterized algorithms and the complexity of edge modification, Unnamed Item, A note on the parameterized complexity of unordered maximum tree orientation, Vertex cover problem parameterized above and below tight bounds, An FPT algorithm for the vertex cover \(P_4\) problem, Circumventing connectivity for kernelization, Unnamed Item, Contracting graphs to paths and trees, A faster FPT algorithm for bipartite contraction, The complexity of König subgraph problems and above-guarantee vertex cover, An improved parameterized algorithm for the independent feedback vertex set problem, Confronting intractability via parameters, The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number, A fixed-parameter algorithm for the vertex cover \(P_3\) problem, Edge bipartization faster than \(2^k\), On feedback vertex set: new measure and new structures, Subset Feedback Vertex Set Is Fixed-Parameter Tractable, Improved FPT Algorithms for Deletion to Forest-Like Structures., An improved FPT algorithm for almost forest deletion problem, Improved algorithms for feedback vertex set problems, Minimization and parameterized variants of vertex partition problems on graphs, On the parameterized complexity of reconfiguration problems, FPT algorithms for connected feedback vertex set, Fixed-parameter enumerability of cluster editing and related problems, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, 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, Iterative Compression and Exact Algorithms, Unnamed Item, A Quartic Kernel for Pathwidth-One Vertex Deletion, An improved FPT algorithm for independent feedback vertex set, Mim-width. II. The feedback vertex set problem, A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems, A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem, Faster graph bipartization, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, Parameterized complexity of finding regular induced subgraphs, Unnamed Item, Incompressibility of \(H\)-free edge modification problems: towards a dichotomy, Unnamed Item, On the complexity of singly connected vertex deletion, Unnamed Item, An Improved Exact Algorithm for Undirected Feedback Vertex Set, An improved exact algorithm for undirected feedback vertex set, On group feedback vertex set parameterized by the size of the cutset

Cites Work

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