Approximability of the independent feedback vertex set problem for bipartite graphs

DOI10.1016/j.tcs.2020.10.026zbMath1471.68210OpenAlexW3095894106MaRDI QIDQ5919046

Takehiro Ito, Xiao Zhou, Yuma Tamura

Publication date: 15 December 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.10.026

zbMATH Keywords

graph algorithmsindependent feedback vertex setbipartite graphs, inapproximability

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On parameterized independent feedback vertex set
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Some APX-completeness results for cubic graphs
• Independent feedback vertex sets for graphs of bounded diameter
• Independent feedback vertex set for \(P_5\)-free graphs
• Faster deterministic \textsc{Feedback Vertex Set}
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Partition the vertices of a graph into one independent set and one acyclic set
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• Planar Formulae and Their Uses
• Approximation algorithms for NP-complete problems on planar graphs
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Recognizing Graphs Close to Bipartite Graphs
• Approximability of the independent feedback vertex set problem for bipartite graphs
• An improved FPT algorithm for independent feedback vertex set

This page was built for publication: Approximability of the independent feedback vertex set problem for bipartite graphs