Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth
share
We study the minimum size f of a feedback vertex set in directed and undirected n-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound k-1/k+1n is known to be tight for graphs with bounded treewidth k or bounded odd degeneracy k. We show that neither of the easy upper and lower bounds k-1/k+1n and k/k+2n can be exact for the case of even degeneracy. More precisely, for even degeneracy k we prove that 3k-2/3k+4n≤ f < k/k+2n. For directed graphs of bounded degeneracy k, we prove that f≤k-1/k+1n and that this inequality is strict when k is odd. For directed graphs of bounded treewidth k≥ 2, we show that k-2⌊log_2(k)⌋/k+1n≤ f ≤k/k+3n. Further, we provide several constructions of low degeneracy or treewidth and large f.
READ FULL TEXT