Strong hardness of approximation for tree transversals

DOI10.1016/j.ipl.2022.106352OpenAlexW4311456155MaRDI QIDQ2681395

Pengxiang Wang, Euiwoong Lee

Publication date: 3 February 2023

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmshardness of approximationvertex deletion\(H\)-transversalhypergraph vertex cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Approximation algorithms for hitting subgraphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Partitioning a Graph into Small Pieces with Applications to Path Transversal
• The approximation of maximum subgraph problems
• Hitting topological minors is FPT
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Inapproximability of $H$-Transversal/Packing

This page was built for publication: Strong hardness of approximation for tree transversals