Feedback Vertex Set in Mixed Graphs

Abstract

A mixed graph is a graph with both directed and undirected edges. We present an algorithm for deciding whether a given mixed graph on $n$ vertices contains a feedback vertex set (FVS) of size at most $k$, in time $2^{O(k)}k!O(n^4)$. This is the first fixed parameter tractable algorithm for FVS that applies to both directed and undirected graphs.

Cited by in corpus (1)

• Backdoors to Satisfaction