Approximability of the independent feedback vertex set problem for bipartite graphs (Q5919046)
From MaRDI portal
scientific article; zbMATH DE number 7285608
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Approximability of the independent feedback vertex set problem for bipartite graphs |
scientific article; zbMATH DE number 7285608 |
Statements
Approximability of the independent feedback vertex set problem for bipartite graphs (English)
0 references
15 December 2020
0 references
The problem dealt with is presented to be NP-hard, even if one restricts to binary planar graphs with maximum degree 4. So only some approximability can be hoped for. The task is to identify an independent vertex set such that -- after cutting it out together with the adjacent edges -- there will remain a forest. Starting with a strengthened inapproximability result, several detailed estimations are presented. The paper contains a bibliography with 23 entries.
0 references
graph algorithms
0 references
independent feedback vertex set
0 references
bipartite graphs, inapproximability
0 references
