Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

DOI10.1137/S0097539796305109zbMath0907.68110OpenAlexW2081880478MaRDI QIDQ4210077

Ron M. Roth, Joseph (Seffi) Naor, Dan Geiger, Reuven Bar Yehuda

Publication date: 20 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796305109

zbMATH Keywords

Bayesian networks combinatorial optimization approximation algorithms constraint satisfaction vertex feedback set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) General topics in artificial intelligence (68T01)

Related Items (52)

Tracking Paths ⋮ The size of graphs with given feedback vertex number ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Feedback vertex set in hypercubes ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Feedback vertex sets in mesh-based networks ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Decycling bipartite graphs ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Feedback numbers of Kautz digraphs ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ New bounds on the decycling number of generalized de Bruijn digraphs ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Unnamed Item ⋮ Fixed-parameter tractability for the subset feedback set problem and the $S$-cycle packing problem ⋮ The decycling number of outerplanar graphs ⋮ The power of linear-time data reduction for maximum matching ⋮ On the decycling number of generalized Kautz digraphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ New formulae for the bipartite vertex frustration and decycling number of graphs ⋮ A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs ⋮ Feedback numbers of de Bruijn digraphs ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs ⋮ Parameterized aspects of triangle enumeration ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Combinatorial algorithms for feedback problems in directed graphs ⋮ Minimum feedback vertex sets in shuffle-based interconnection networks ⋮ Unnamed Item ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ 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 ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

This page was built for publication: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference