An FPT algorithm for the vertex cover P₄ problem

DOI10.1016/J.DAM.2015.06.032zbMATH Open1329.05287OpenAlexW880397381MaRDI QIDQ906446FDOQ906446

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

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

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)

Cites Work

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

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

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)