Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem

Lemaic, Mile and Speckenmeyer, Ewald (2009) Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem.
Technical Report , 21 p.


Let G be a directed graph. A vertex set F is called feedback vertex set (FVS) if its removal from G results in an acyclic graph. Because determining a minimum cardinality FVS is known to be NP hard, [Karp72], one is interested in designing fast approximation algorithms determining near-optimum FVSs. The paper presents deterministic and randomised heuristics based on Markov chains. In this regard, an earlier approximation algorithm developed in [Speckenmeyer89] is revisited and refined. Experimental results demonstrate the overall performance superiority of our algorithms compared to other algorithms known from literature with respect to both criteria, the sizes of solutions determined, as well as the consumed runtimes.

Download: [img] Postscript
Download (405kB) | Preview
Download: [img] PDF
Download (168kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2010-596
Depositing User: Mile Lemaic
Date Deposited: 08 Jan 2010 00:00
Last Modified: 19 Dec 2011 09:44