Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth (Q2094884)

Summary: 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 \(\frac{k-1}{k+1}n\) 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 \(\frac{k-1}{k+1}n\) and \(\frac{k}{k+2}n\) can be exact for the case of even degeneracy. More precisely, for even degeneracy \(k\) we prove that \(f < \frac{k}{k+2}n\) and for every \(\epsilon>0\), there exists a \(k\)-degenerate graph for which \(f\geqslant \frac{3k-2}{3k+4}n -\epsilon\). For directed graphs of bounded degeneracy \(k\), we prove that \(f\leqslant\frac{k-1}{k+1}n\) and that this inequality is strict when \(k\) is odd. For directed graphs of bounded treewidth \(k\geqslant 2\), we show that \(f \leqslant \frac{k}{k+3}n\) and for every \(\epsilon>0\), there exists a \(k\)-degenerate graph for which \(f\geqslant \frac{k-2\lfloor\log_2(k)\rfloor}{k+1}n -\epsilon\). Further, we provide several constructions of low degeneracy or treewidth and large \(f\).