论文标题
击中子图的近似算法
Approximation algorithms for hitting subgraphs
论文作者
论文摘要
令$ h $为$ k $顶点上的固定无向图。 $ h $键入的设置问题要求从给定的图形$ g $中删除最少数量的顶点，以至于所得的图形没有$ h $作为子图的副本。这个问题是$ K $均匀的超图上的HyperGraph顶点覆盖问题的特殊情况，因此接受有效的$ K $ -FACTOR近似算法。本文的目的是调查一个问题，即可以改善这个微不足道的近似因子$ k $。
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.
