A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
From MaRDI portal
Publication:4699157
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)
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)
MIP formulations for induced graph optimization problems: a tutorial ⋮ Approximating power node-deletion problems ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes ⋮ Spin Glass approach to the feedback vertex set problem ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Connected feedback vertex set on AT-free graphs ⋮ Unnamed Item ⋮ Minimization and parameterized variants of vertex partition problems on graphs ⋮ 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
This page was built for publication: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
