On feedback vertex set: new measure and new structures

DOI10.1007/S00453-014-9904-6zbMATH Open1327.05318arXiv1004.1672OpenAlexW3101258912MaRDI QIDQ494933FDOQ494933

Authors: Yixin Cao, Yang Liu, Jianer Chen 

Publication date: 3 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We present a new parameterized algorithm for the {feedback vertex set} problem ({sc fvs}) on undirected graphs. We approach the problem by considering a variation of it, the {disjoint feedback vertex set} problem ({sc disjoint-fvs}), which finds a feedback vertex set of size $k$ that has no overlap with a given feedback vertex set $F$ of the graph $G$. We develop an improved kernelization algorithm for {sc disjoint-fvs} and show that {sc disjoint-fvs} can be solved in polynomial time when all vertices in $GsetminusF$ have degrees upper bounded by three. We then propose a new branch-and-search process on {sc disjoint-fvs}, and introduce a new branch-and-search measure. The process effectively reduces a given graph to a graph on which {sc disjoint-fvs} becomes polynomial-time solvable, and the new measure more accurately evaluates the efficiency of the process. These algorithmic and combinatorial studies enable us to develop an $O^{\ast }(3.83^k)$-time parameterized algorithm for the general {sc fvs} problem, improving all previous algorithms for the problem.

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

Recommendations

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

zbMATH Keywords

cubic graphsparameterized computationcographic matroiddisjoint feedback vertex setkernlizationmatroid intersection problemmeasure and bound

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Finding odd cycle transversals.
• 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
• Title not available (Why is that?)
• ON DISJOINT CYCLES
• Title not available (Why is that?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Lower bounds based on the exponential time hypothesis
• Parameterized and Exact Computation
• Title not available (Why is that?)
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• 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
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• Title not available (Why is that?)
• Faster deterministic \textsc{Feedback Vertex Set}
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (30)

• 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
• Improved FPT Algorithms for Deletion to Forest-Like Structures.
• Title not available (Why is that?)
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• An improved FPT algorithm for independent feedback vertex set
• Sublinear approximation algorithms for boxicity and related problems
• On the Complexity of Singly Connected Vertex Deletion
• Improved analysis of highest-degree branching for feedback vertex set
• An improved FPT algorithm for almost forest deletion problem
• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
• On feedback vertex set new measure and new structures
• MIP formulations for induced graph optimization problems: a tutorial
• FPT algorithms for generalized feedback vertex set problems
• Parameterized complexity of fair feedback vertex set problem
• Parameterized Complexity of Fair Feedback Vertex Set Problem
• Fixed parameterized algorithms for generalized feedback vertex set problems
• Odd cycle transversal in mixed graphs
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• On the complexity of singly connected vertex deletion
• FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters
• A polynomial kernel for block graph deletion
• Structural Parameterizations of Feedback Vertex Set
• Faster deterministic \textsc{Feedback Vertex Set}
• A naive algorithm for feedback vertex set
• Solving problems on graphs of high rank-width
• Two Hardness Results on Feedback Vertex Sets
• Feedback Vertex Sets on Tree Convex Bipartite Graphs

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

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