Approximation algorithms for hitting subgraphs

November 29, 2020 Β· Declared Dead Β· πŸ› International Workshop on Combinatorial Algorithms

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Noah BrΓΌstle, Tal Elbaz, Hamed Hatami, Onur Kocer, Bingchan Ma arXiv ID 2011.14450 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM Citations 4 Venue International Workshop on Combinatorial Algorithms Last Checked 4 months ago
Abstract
Let $H$ be a fixed undirected graph on $k$ vertices. The $H$-hitting set problem asks for deleting a minimum number of vertices from a given graph $G$ in such a way that the resulting graph has no copies of $H$ as a subgraph. This problem is a special case of the hypergraph vertex cover problem on $k$-uniform hypergraphs, and thus admits an efficient $k$-factor approximation algorithm. The purpose of this article is to investigate the question that for which graphs $H$ this trivial approximation factor $k$ can be improved.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted