Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436296 | Theoretical Computer Science | 2014 | 9 Pages |
Abstract
A feedback vertex set of a graph G is a set S of its vertices such that the subgraph induced by V(G)∖SV(G)∖S is a forest. The cardinality of a minimum feedback vertex set of G is denoted by ∇(G)∇(G). A graph G is 2-degenerate if each subgraph G′G′ of G has a vertex v such that dG′(v)≤2dG′(v)≤2.In this paper, we prove that ∇(G)≤2n/5∇(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/52n/5.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mieczysław Borowiecki, Ewa Drgas-Burchardt, Elżbieta Sidorowicz,