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

Abstract

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, the algorithm runs in $O(km\sqrt{n})$ time and improves upon the previously best-known approximation ratio of $1+\frac{k}{k+1}$ established by Kumar et al. [Theoretical Computer Science, 526: 90--96 (2014)]. Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of König-Egerváry graphs.