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

2021/10/05 by Seyedmohammadhossein Hosseinian, Hosseinian, Seyedmohammadhossein, Sergiy Butenko +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2110.02487

openalex publication_date 2021/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a (1+\(k)/(k+2))-approximation algorithm for the Maximum\nk-dependent Set problem on bipartite graphs for any k\≥1. For a graph with\nn vertices and m edges, the algorithm runs in O(k m \√(n)) time and\nimproves upon the previously best-known approximation ratio of\n1+\(k)/(k+1) established by Kumar et al. [Theoretical Computer Science,\n526: 90--96 (2014)]. Our proof also indicates that the algorithm retains its\napproximation ratio when applied to the (more general) class of\nK "onig-Egerv 'ary graphs.\n

Citations

• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Cited by

• Sharp lower bounds and extremal graphs for the generalized k-independence number
• A sharp lower bound on the generalized 4-independence number

Related

• Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio~0.7
• Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
• Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
• Greedy domination on biclique-free graphs
• Improved Combinatorial Approximation Algorithms for MAX CUT in Sparse Graphs