2022 journal article
An improved approximation for Maximum k-dependent Set on bipartite graphs
Discrete Applied Mathematics.
open access via manuscript.elsevier.com (publisher PDF)
Source: ORCID
Added: August 15, 2024
We present a (1+kk+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(kmn) time and improves upon the previously best-known approximation ratio of 1+kk+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 König–Egerváry graphs.