An Improved Approximation for Maximum $k$-Dependent Set on Bipartite Graphs

Seyedmohammadhossein Hosseinian, Sergiy Butenko

We present a $(1+\frac{k}{k+2})$-approximation algorithm for the Maximum $k$-dependent Set problem on bipartite graphs for any $k\ge 1$. For a graph with $n$ vertices and $m$ edges,…