Approximation algorithms for hitting subgraphs

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

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

hitting setsvertex coversubgraph elimination

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Strong hardness of approximation for tree transversals

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

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