feedback vertex set

• 2019 Sorge2019
  • page 10 : feedback vertex set $k$ upper bounds distance to chordal by $\mathcal O(k)$ – Lemma 4.20. The feedback edge set number $f$ upper bounds the distance to a chordal graph $c$. We have $c \le f$.
• https://en.wikipedia.org/wiki/Feedback_vertex_set
  • feedback vertex set – … a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles… . The feedback vertex set number of a graph is the size of a smallest feedback vertex set.
• unknown
  • feedback edge set $k$ upper bounds feedback vertex set by $\mathcal O(k)$ – Given solution to feedback edge set one can remove one vertex incident to the solution edges to obtain feedback vertex set.
  • feedback vertex set – can be thought of as a distance to forest
  • feedback vertex set is equal to distance to forest