Forest covers

doi:10.1016/j.tcs.2026.115988

Forest covers

2026-05-01

0

PRE

AI

DOI：10.1016/j.tcs.2026.115988

Original

Original request for help

Save

Abstract

En 中文

We study approximation algorithms for the forest cover and bounded forest cover problems. A probabilistic 3 + epsilon approximation algorithm for the forest cover problem is given using the method of dual fitting. A deterministic algorithm with a 2-approximation ratio that rounds the optimal solution to a linear program is given next. The 2-approximation for the forest cover is then used to give a 6-approximation for the bounded forest cover problem. The use of the probabilistic method to develop the 3 + epsilon approximation algorithm may be of independent interest.

Keywords:

Vertex cover

Forest cover

Approximation algorithm

Randomized algorithm

Linear programming

Dual fitting

LP rounding

Forest covers

Abstract

Journal

Organization

Cited Papers