Approximation algorithms for hitting subgraphs

DOI10.1007/978-3-030-79987-8_26OpenAlexW3183859668MaRDI QIDQ2115875

Noah Brüstle, Bingchan Ma, Onur Kocer, Hamed Hatami, Tal Elbaz

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/2011.14450

zbMATH Keywords

vertex coverhitting setssubgraph elimination

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Strong hardness of approximation for tree transversals

Cites Work

• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A faster FPT algorithm for 3-path vertex cover
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Improved approximation algorithms for hitting 3-vertex paths
• Minimum \(k\)-path vertex cover
• Partitioning a graph into small pieces with applications to path transversal
• On the vertex \(k\)-path cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Inapproximability of $H$-Transversal/Packing

This page was built for publication: Approximation algorithms for hitting subgraphs