On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
type: Item
instance of: scholarly article
title: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
zbMATH Open document ID: 0678.05026
DOI: 10.1016/0012-365X(88)90226-9
author: Shuichi Ueno
author: Yoji Kajitani
author: Shin'ya Gotoh
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: For a graph \(G=(V,E)\) and a set \(S\subset V\) let G-S be the graph obtained from G by deleting the vertices in S. A set of vertices F is called a feedback set of G if G-F contains no circuit. The feedback set problem is to find a minimum feedback set. It is known both the nonseparating independent set problem (to find the maximum independent set which contains no separating sets) and feedback set problem are NP- complete graph problems. In the paper these problems for graphs with no vertex degree exceeding 3 are reduced to the corresponding problems for 3-regular graphs, and then to the matching problem and the spanning set problem of some linearly represented 2-polymatroid, respectively, for which Lovászś polynomial-time algorithms are known.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4110719
zbMATH Keywords: feedback set problem
zbMATH Keywords: minimum feedback set
zbMATH Keywords: nonseparating independent set
zbMATH Keywords: NP-complete graph problems
zbMATH Keywords: 3-regular graphs
zbMATH Keywords: matching problem
zbMATH Keywords: spanning set problem
Wikidata QID: Q59442098
MaRDI profile type: Publication
cites work: Some simplified NP-complete graph problems
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Q3934404
cites work: Q3739144
full work available at URL: 0012-365x(88)90226-9
OpenAlex ID: W2069169607
description: scientific article; zbMATH DE number 4110719