Phase transition in the bipartite z-matching

Abstract

We study numerically the maximum $z$-matching problems on ensembles of bipartite random graphs. The $z$-matching problems describes the matching between two types of nodes, users and servers, where each server may serve up to $z$ users at the same time. By using a mapping to standard maximum-cardinality matching, and because for the latter there exists a polynomial-time exact algorithm, we can study large system sizes of up to $10^6$ nodes. We measure the capacity and the energy of the resulting optimum matchings. First, we confirm previous analytical results for bipartite regular graphs. Next, we study the finite-size behaviour of the matching capacity and find the same scaling behaviour as before for standard matching, which indicates the universality of the problem. Finally, we investigate for bipartite Erdős-Rényi random graphs the saturability as a function of the average degree, i.e., whether the network allows as many customers as possible to be served, i.e. exploiting the servers in an optimal way. We find phase transitions between unsaturable and saturable phases. These coincide with a strong change of the running time of the exact matching algorithm, as well with the point where a minimum-degree heuristic algorithm starts to fail.

arXiv comment10 pages, 9 figures, 3 tables

References in corpus (22)

• Random graphs with arbitrary degree distributions and their applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Phase Transition in the Number Partitioning Problem
• Coloring random graphs
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• The number of matchings in random graphs
• Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Scaling hypothesis for the Euclidean bipartite matching problem
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Random multi-index matching problems
• autoScale.py - A program for automatic finite-size scaling analyses: A user's guide
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Comparing Mean Field and Euclidean Matching Problems
• On the finite size corrections to some random matching problems
• Bias in generation of random graphs
• Numerical Solution-Space Analysis of Satisfiability Problems
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• Statistical mechanics of bipartite $z$-matchings
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem

Cited by in corpus (1)

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