An FPT algorithm for the vertex cover \(P_4\) problem

DOI10.1016/j.dam.2015.06.032zbMath1329.05287OpenAlexW880397381MaRDI QIDQ906446

Ze-min Jin, Jian-hua Tu

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

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

Related Items (5)

An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Unnamed Item ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Finding odd cycle transversals.
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• Fixed-parameter algorithms for cluster vertex deletion
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On the \(k\)-path vertex cover of some graph products
• Minimum \(k\)-path vertex cover
• Another disjoint compression algorithm for odd cycle transversal
• On the vertex \(k\)-path cover
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

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