An FPT algorithm for the vertex cover P₄ problem

DOI10.1016/J.DAM.2015.06.032MaRDI QIDQ906446zbMATH OpenOpenAlexFDO

Authors Jianhua Tu, Zemin Jin

Publication date 21 January 2016

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

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

zbMATH Keywords

graph algorithmsparameterized complexityiterative compressionvertex cover \(P_4\) problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• A faster FPT algorithm for 3-path vertex cover

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Another disjoint compression algorithm for odd cycle transversal
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Finding odd cycle transversals.
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph theory
• Improved algorithms for feedback vertex set problems
• Minimum \(k\)-path vertex cover
• On the k-path vertex cover of some graph products
• On the vertex \(k\)-path cover
• On the weighted \(k\)-path vertex cover problem
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(12)

• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Hitting subgraphs in \(P_4\)-tidy graphs
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• Faster parameterized algorithms for two vertex deletion problems
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
• Generating Faster Algorithms for d-Path Vertex Cover
• Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
• Faster FPT algorithm for 5-path vertex cover

This page was built for publication: An FPT algorithm for the vertex cover \(P_4\) problem

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