An approximation algorithm for finding a $\{C_4,P_5\}$-hitting set of the minimal weight in a graph

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk

Abstract: The problem of removing the minimal number of vertices of a given graph so that the resulting graph contains no cycles $C_4$ on 4 vertices and no paths $P_5$ on 5 vertices as subgraphs is considered. A 4-approximation algorithm for this problem is described.

UDC: 519.1