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.

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