On feedback vertex set: new measure and new structures

DOI10.1007/S00453-014-9904-6MaRDI QIDQ494933zbMATH OpenOpenAlexFDO

Authors Yixin Cao, Yang Liu, Jianer 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 graphsparameterized computationcographic matroiddisjoint feedback vertex setkernlizationmatroid intersection problemmeasure and bound

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3848625 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 512804 (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 3215864 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Finding odd cycle transversals.
• Improved algorithms for feedback vertex set problems
• Lower bounds based on the exponential time hypothesis
• Nonconstructive tools for proving polynomial-time decidability
• ON DISJOINT CYCLES
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• 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
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parameterized and Exact Computation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

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.
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• scientific article; zbMATH DE number 7650230 (Why is no real title available?)
• An improved FPT algorithm for independent feedback vertex set
• Sublinear approximation algorithms for boxicity and related problems
• Improved analysis of highest-degree branching for feedback vertex set
• An improved FPT algorithm for almost forest deletion problem
• On the Complexity of Singly Connected Vertex Deletion
• FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
• 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
• Fixed parameterized algorithms for generalized feedback vertex set problems
• Parameterized Complexity of Fair Feedback Vertex Set Problem
• Odd cycle transversal in mixed graphs
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• On the complexity of singly connected vertex deletion
• Improved FPT Algorithms for Deletion to Forest-Like Structures
• 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)