On 14.10.2010 at 12:20 in S11, there is the following noon lecture:
Feedback vertex set in mixed graphs
Computer Science Department, Humboldt University Berlin
For many algorithmic graph problems, the problem variant for directed graphs is strictly harder than the one for undirected graphs (consider for instance Shortest Path, Longest Path, Dominating Set). That is, an algorithm for the directed problem variant can easily be used to solve the undirected problem variant: simply replace undirected edges by a pair of directed edges in both directions.
The Feedback Vertex Set (FVS) problem is an exception to this pattern. This decision problem asks, given a (possibly directed) graph G and integer k, whether there is a set of at most k vertices that hits all cycles of G. We are interested in Fixed Parameter Tractable (FPT) algorithms for this problem: algorithms with complexity bounded by f(k)*O(n^c), where n is the number of vertices of G, c is a constant independent of k, and f(k) may be an arbitrary computable function.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019