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

DOI10.1016/J.DAM.2021.10.015MaRDI QIDQ2057593zbMATH OpenOpenAlexFDO

Authors Seyedmohammadhossein Hosseinian, Sergiy Butenko

Publication date 7 December 2021

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

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

Cites work

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

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)