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.

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 |