A local algorithm and its percolation analysis of bipartite $z$-matching problem

Abstract

A $z$-matching on a bipartite graph is a set of edges, among which each vertex of two types of the graph is adjacent to at most $1$ and at most $z$ ($⩾1$) edges, respectively. The $z$-matching problem concerns finding $z$-matchings with the maximum size. Our approach to this combinatorial optimization problem is twofold. From an algorithmic perspective, we adopt a local algorithm as a linear approximate solver to find $z$-matchings on any graph instance, whose basic component is a generalized greedy leaf removal procedure in graph theory. From a theoretical perspective, on uncorrelated random bipartite graphs, we develop a mean-field theory for percolation phenomenon underlying the local algorithm, leading to an analytical estimation of $z$-matching sizes on random graphs. Our analytical theory corrects the prediction by belief propagation algorithm at zero-temperature limit in (Kreačić and Bianconi 2019 \textsl{EPL} \textbf{126} 028001). Besides, our theoretical framework extends a core percolation analysis of $k$-XORSAT problems to a general context of uncorrelated random hypergraphs with arbitrary degree distributions of factor and variable nodes.

32 pages, including 7 figures and 2 tables

References in corpus (11)

• Networks beyond pairwise interactions: structure and dynamics
• The physics of higher-order interactions in complex systems
• Core percolation on complex networks
• Covering Problems and Core Percolations on Hypergraphs
• Generalization of core percolation on complex networks
• Statistical Mechanics of the Minimum Dominating Set Problem
• Controllability and maximum matchings of complex networks
• Maximum matching on random graphs
• Two faces of greedy leaf removal procedure on graphs
• Statistical mechanics of bipartite $z$-matchings
• Phase transition in the bipartite z-matching

Cited by in corpus (1)

• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods