A local algorithm and its percolation analysis of bipartite -matching problem
arXiv:1812.03442 · doi:10.1088/1742-5468/acd105
Abstract
A -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 and at most () edges, respectively. The -matching problem concerns finding -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 -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 -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 -XORSAT problems to a general context of uncorrelated random hypergraphs with arbitrary degree distributions of factor and variable nodes.
arXiv comment32 pages, including 7 figures and 2 tables
References in corpus (27)
- Emergence of scaling in random networks
- Spatial Networks
- Networks beyond pairwise interactions: structure and dynamics
- Dynamical and correlation properties of the Internet
- Universal Behavior of Load Distribution in Scale-free Networks
- The physics of higher-order interactions in complex systems
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- The number of matchings in random graphs
- Simplest random K-satisfiability problem
- Core percolation on complex networks
- Core percolation in random graphs: a critical phenomena analysis
- Exact solutions for diluted spin glasses and optimization problems
- Covering Problems and Core Percolations on Hypergraphs
- Analytic solution of a static scale-free network model
- Generalization of core percolation on complex networks
- Statistical Mechanics of the Minimum Dominating Set Problem
- Intrinsic degree-correlations in static model of scale-free networks
- Controllability and maximum matchings of complex networks
- Core percolation and onset of complexity in Boolean networks
- Maximum matching on random graphs
- The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
- Core organization of directed complex networks
- The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
- Two faces of greedy leaf removal procedure on graphs
- Statistical mechanics of bipartite -matchings
- Phase transition in the bipartite z-matching