A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

DOI10.1137/S0895480196305124zbMath0932.68054MaRDI QIDQ4699157

Toshihiro Fujito, Vineet Bafna, Piotr Berman

Publication date: 23 November 1999

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmperformance guaranteefeedback vertex set problemlocal ratio theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (only showing first 100 items - show all)

Flexible bandwidth assignment with application to optical networks ⋮ Tracking Paths ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ On residual approximation in solution extension problems ⋮ Scattered packings of cycles ⋮ An efficient approximation for the generalized assignment problem ⋮ Polynomial time algorithms for tracking path problems ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ Efficient approximation of convex recolorings ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ On line graphs of subcubic triangle-free graphs ⋮ Simultaneous feedback edge set: a parameterized perspective ⋮ Decycling bipartite graphs ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Parameterized complexity of secluded connectivity problems ⋮ Feedback numbers of Kautz digraphs ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Approximation algorithms for orienting mixed graphs ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Tracking paths ⋮ A polynomial kernel for 3-leaf power deletion ⋮ Tight Localizations of Feedback Sets ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Improved kernels for tracking paths ⋮ Refining the complexity of the sports elimination problem ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ On Residual Approximation in Solution Extension Problems ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Circumventing connectivity for kernelization ⋮ Unnamed Item ⋮ Tradeoffs in process strategy games with application in the WDM reconfiguration problem ⋮ Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ The vertex cover \(P_3\) problem in cubic graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem ⋮ Improved approximation algorithm for convex recoloring of trees ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ The decycling number of generalized Petersen graphs ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ A spin glass approach to the directed feedback vertex set problem ⋮ Decycling bubble sort graphs ⋮ On feedback vertex set: new measure and new structures ⋮ On the tractability of \(( k , i )\)-coloring ⋮ Efficient algorithm for the vertex cover \(P_k\) problem on cacti ⋮ MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS ⋮ Feedback vertex set on AT-free graphs ⋮ Admission control with advance reservations in simple networks ⋮ Approximation Algorithms for Orienting Mixed Graphs ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Improved algorithms for feedback vertex set problems ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Combination of parallel machine scheduling and vertex cover ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ Unnamed Item ⋮ Feedback numbers of de Bruijn digraphs ⋮ Unnamed Item ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Minimum feedback vertex sets in shuffle-based interconnection networks ⋮ Unnamed Item ⋮ Approximation Algorithms for Minimum Chain Vertex Deletion ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ A polynomial sized kernel for tracking paths problem ⋮ Achieving a global objective with competing networked agents in the framework of discrete event systems ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Resource allocation in bounded degree trees ⋮ Feedback vertex sets in star graphs ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ On the complexity of singly connected vertex deletion ⋮ New bounds on the size of the minimum feedback vertex set in meshes and butterflies. ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ An improved exact algorithm for undirected feedback vertex set ⋮ Improved approximation for orienting mixed graphs ⋮ MIP formulations for induced graph optimization problems: a tutorial

This page was built for publication: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem