# zbMATH — the first resource for mathematics

On feedback problems in digraphs. (English) Zbl 0768.68181
Graph-theoretic concepts in computer science, Proc. 15th Int. Workshop, WG ’89, Castle Rolduc/Neth. 1989, Lect. Notes Comput. Sci. 411, 218-231 (1990).
Summary: [For the entire collection see Zbl 0759.00013.]
A subset $$F\subseteq V$$ of vertices of a digraph $$G=(V,A)$$ with $$n$$ vertices and $$m$$ arcs, is called a feedback vertex set (fvs), if $$G-F$$ is an acyclic digraph (dag). The main results in this paper are:
(1) An $$O(n^ 2 m)$$ simplification procedure is developed and it is shown that the class of digraphs, for which a minimum fvs is determined by this procedure alone, properly contains two classes for which minimum fvs’s are known to be computable in polynomial time, see A. Shamir [SIAM J. Comput. 8, 645-655 (1979; Zbl 0422.05029)] and C.-C. Wang, E. L. Lloyd and M. L. Soffa [J. Assoc. Comput. Mach. 32, 296- 313 (1985; Zbl 0633.68064)].
(2) A new $$O(n^ 3\cdot| F|)$$ approximation algorithm MFVS for the fvs-problem is proposed, which iteratively deletes in each step a vertex with smallest mean return time during a random walk in the digraph. It is shown that MFVS applied to symmetric digraphs determines a solution of worst case ratio bounded by $$O(\log n)$$. The quality of fvs’s produced by MFVS is compared to those produced by Rosen’s fvs-algorithm, see B. K. Rosen [J. Algorithms 3, 205-217 (1982; Zbl 0493.68065)], for series of randomly generated digraphs.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity 05C20 Directed graphs (digraphs), tournaments 60G50 Sums of independent random variables; random walks