Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs

DOI10.1016/j.dam.2014.10.033zbMath1311.05088OpenAlexW1987064693MaRDI QIDQ2341756

Sounaka Mishra, N. Safina Devi, Aniket Mane

Publication date: 28 April 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.033

zbMATH Keywords

approximation algorithmregular graph\(K_{1,4}\)-free graph\(P_4\) vertex cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Approximation algorithms (68W25)

Related Items

Approximating Bounded Degree Deletion via Matroid Matching, On the König graphs for a 5-path and its spanning supergraphs, Analyzing the 3-path vertex cover problem in planar bipartite graphs, Improved approximation algorithms for path vertex covers in regular graphs, Approximation algorithms for minimum weight connected 3-path vertex cover, Kernels for packing and covering problems, König Graphs with Respect to the 4-Path and Its Spanning Supergraphs, On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A new approach for approximating node deletion problems
• The node-deletion problem for hereditary properties is NP-complete
• Optimization, approximation, and complexity classes
• A unified approximation algorithm for node-deletion problems
• Some APX-completeness results for cubic graphs
• Minimum \(k\)-path vertex cover
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A better approximation ratio for the vertex cover problem
• Node-Deletion Problems on Bipartite Graphs
• On the hardness of approximating minimization problems