feedback edge set

• 2022/09 Tran2022
  • page 32 : feedback edge set $k$ upper bounds c-closure by $\mathcal O(k)$ – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
  • page 32 : bounded c-closure does not imply bounded feedback edge set – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
• 2019 Sorge2019
  • page 10 : feedback edge set $k$ upper bounds genus by $\mathcal O(k)$ – Lemma 4.19. The feedback edge set number $f$ upper bounds the genus $g$. We have $g \le f$.
• SchroderThesis
  • page 23 : bounded feedback edge set does not imply bounded pathwidth – Proposition 3.16
  • page 25 : bounded feedback edge set does not imply bounded distance to interval – Proposition 3.21
  • page 25 : bounded feedback edge set does not imply bounded h-index – Proposition 3.22
  • page 30 : bounded feedback edge set does not imply bounded bisection bandwidth – Proposition 3.29
• 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 edge set $k$ upper bounds genus by $\mathcal O(k)$ – Removing $k$ edges creates a forest that is embeddable into the plane. We now add one handle for each of the $k$ edges to get embedding into $k$-handle genus.
  • maximum leaf number $k$ upper bounds feedback edge set by $f(k)$
  • feedback edge set $k$ upper bounds c-closure by $f(k)$
  • forest upper bounds feedback edge set by a constant
  • maximum leaf number $k$ upper bounds feedback edge set by $k^{\mathcal O(1)}$ – M. Bentert (personal communication)
• https://stackoverflow.com/questions/10791689/how-to-find-feedback-edge-set-in-undirected-graph
  • feedback edge set – Let $G=(V,E)$ be an undirected graph. A set $F \subseteq E$ of edges is called a feedback-edge set if every cycle of $G$ has at least one edge in $F$.