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

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

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

• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Cycle transversals in perfect graphs and cographs
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
• Independent Feedback Vertex Set for P₅-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

(26)

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

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)