×

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
PDF BibTeX XML Cite