On feedback vertex set: new measure and new structures

DOI10.1007/s00453-014-9904-6zbMath1327.05318arXiv1004.1672OpenAlexW3101258912MaRDI QIDQ494933

Yixin Cao, Yang Liu, Jian'er Chen

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.1672

zbMATH Keywords

cubic graphsmatroid intersection problemparameterized computationcographic matroiddisjoint feedback vertex setkernlizationmeasure and bound

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

A parameterized complexity view on collapsing \(k\)-cores ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Parameterized Complexity of Fair Feedback Vertex Set Problem ⋮ Parameterized complexity of fair feedback vertex set problem ⋮ A polynomial kernel for block graph deletion ⋮ Odd cycle transversal in mixed graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Unnamed Item ⋮ Solving problems on graphs of high rank-width ⋮ A naive algorithm for feedback vertex set ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ On the complexity of singly connected vertex deletion ⋮ FPT algorithms for generalized feedback vertex set problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• Faster deterministic \textsc{Feedback Vertex Set}
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Nonconstructive tools for proving polynomial-time decidability
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• ON DISJOINT CYCLES
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: On feedback vertex set: new measure and new structures