A feedback vertex set of 2-degenerate graphs

作者：Borowiecki Mieczyslaw; Drgas Burchardt Ewa; Sidorowicz Elzbieta^*

来源：Theoretical Computer Science, 2014, 557: 50-58.

DOI：10.1016/j.tcs.2014.08.016

• Feedback vertex set
• Decycling set
• 2-Degenerate graphs

A feedback vertex set of a graph G is a set S of its vertices such that the subgraph induced by V(G) \ S is a forest. The cardinality of a minimum feedback vertex set of G is denoted by del(G). A graph G is 2-degenerate if each subgraph G' of G has a vertex v such that d(G')(v) <= 2.
In this paper, we prove that del(G) <= 2n/5 for any 2-degenerate n-vertex graph G and moreover, we show that this bound is tight. As a consequence, we derive a polynomial time algorithm, which for a given 2-degenerate n-vertex graph returns its feedback vertex set of cardinality at most 2n/5.

• 出版日期2014-11-6