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

Abstract We present a ( 1 + k k + 2 ) -approximation algorithm for the Maximum k - dependent Set problem on bipartite graphs for any k ≥ 1 . For a graph with n vertices and m edges, the algorithm runs in O ( k m n ) time and improves upon the previously best-known approximation ratio of 1 + k k + 1 established by Kumar et al. (2014). Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of Konig–Egervary graphs.