Independent feedback vertex sets for graphs of bounded diameter

DOI10.1016/J.IPL.2017.11.004MaRDI QIDQ1685021zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Konrad Dabrowski, Carl Feghali, Matthew Johnson, Daniël Paulusma

Publication date 13 December 2017

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1707.09383

zbMATH Keywords

computational complexitydiameterindependent feedback vertex setnear-bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets $A$ and $B$, where $A$ is an independent set and $B$ induces a forest. The set $A$ in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2.

Recommendations

• Recognizing Graphs Close to Bipartite Graphs
• Approximability of the independent feedback vertex set problem for bipartite graphs
• Partition the vertices of a graph into one independent set and one acyclic set
• Feedback vertex sets on restricted bipartite graphs
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Cycle transversals in perfect graphs and cographs
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Independent Feedback Vertex Set for P_5-free Graphs
• On parameterized independent feedback vertex set
• Open problems on graph coloring for special graph classes
• Partition the vertices of a graph into one independent set and one acyclic set
• Recognizing Graphs Close to Bipartite Graphs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• The complexity of surjective homomorphism problems-a survey
• Three complexity results on coloring \(P_k\)-free graphs
• Vertex arboricity and maximum degree

Cited in

(23)

• On parameterized independent feedback vertex set
• Graph-Theoretic Concepts in Computer Science
• Partitioning \(P_4\)-tidy graphs into a stable set and a forest
• Degree-constrained 2-partitions of graphs
• Sparsity in covering solutions
• Acyclic, star, and injective colouring: bounding the diameter
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Partition the vertices of a graph into one independent set and one acyclic set
• Recognizing Graphs Close to Bipartite Graphs
• Faster 3-coloring of small-diameter graphs
• Independent Feedback Vertex Set for P_5-free Graphs
• Sparse graphs are near-bipartite
• Independent feedback vertex set for \(P_5\)-free graphs
• scientific article; zbMATH DE number 7378380 (Why is no real title available?)
• Complexity of near-3-choosability problem
• Domination number and feedback vertex number of complements of line graphs
• Approximability of the independent feedback vertex set problem for bipartite graphs
• Acyclic, star, and injective colouring: bounding the diameter
• Partitioning \(H\)-free graphs of bounded diameter
• Bounding the feedback vertex number of digraphs in terms of vertex degrees

This page was built for publication: Independent feedback vertex sets for graphs of bounded diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685021)