Approximation algorithms for hitting subgraphs

DOI10.1007/978-3-030-79987-8_26MaRDI QIDQ2115875zbMATH OpenOpenAlexFDO

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

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 factor 2 approximation algorithm for the vertex cover P₃ problem
• 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
• Inapproximability of \(H\)-transversal/packing
• Minimum \(k\)-path vertex cover
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the vertex \(k\)-path cover
• Partitioning a graph into small pieces with applications to path transversal
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

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)