An improved approximation for maximum k-dependent set on bipartite graphs

DOI10.1016/J.DAM.2021.10.015zbMATH Open1481.90276arXiv2110.02487OpenAlexW3212078225MaRDI QIDQ2057593FDOQ2057593

Authors: Seyedmohammadhossein Hosseinian, Sergiy Butenko 

Publication date: 7 December 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We present a $(1+frackk+2)$-approximation algorithm for the Maximum $k$-dependent Set problem on bipartite graphs for any $kge1$. For a graph with $n$ vertices and $m$ edges, the algorithm runs in $O(kmsqrtn)$ time and improves upon the previously best-known approximation ratio of $1+frackk+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"{o}nig-Egerv'{a}ry graphs.

Full work available at URL: https://arxiv.org/abs/2110.02487

Recommendations

• A 0.821-ratio purely combinatorial algorithm for maximum \(k\)-vertex cover in bipartite graphs
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem

zbMATH Keywords

approximation algorithmsbipartite graphsmaximum \(k\)-dependent setKönig-Egerváry graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• A Separator Theorem for Planar Graphs
• Title not available (Why is that?)
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• Title not available (Why is that?)
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• A characterization of the graphs in which the transversal number equals the matching number
• The Co-2-plex Polytope and Integral Systems
• Improper coloring of unit disk graphs
• Title not available (Why is that?)
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• Polyhedral properties of the induced cluster subgraphs
• The maximum independent union of cliques problem: complexity and exact approaches
• A short proof of K�nig's matching theorem

Cited In (5)

• Maximum weight t-sparse set problem on vector-weighted graphs
• A bound on the dissociation number
• Locally defined independence systems on graphs
• Relating the independence number and the dissociation number
• Relating dissociation, independence, and matchings

This page was built for publication: An improved approximation for maximum \(k\)-dependent set on bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2057593)