We analyse the asymptotic behaviour of random instances of the maximum set packing (MSP) optimization problem, also known as maximum matching or maximum strong independent set on hypergraphs. We give an analytic prediction of the MSPs size using the 1RSB cavity method from statistical mechanics of disordered systems. We also propose a heuristic algorithm, a generalization of the celebrated Karp-Sipser one, which allows us to rigorously prove that the replica symmetric cavity method prediction is exact for certain problem ensembles and breaks down when a core survives the leaf removal process. The -phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized to for one of the ensembles considered, where is the size of the sets. 1. Introduction The maximum set packing is a very much studied problem in combinatorial optimization, one of Karp’s twenty-one NP-complete problems. Given a set and a collection of its subsets labeled by ; a set packing (SP) is a collection of the subsets such that they are pairwise disjoint. The size of a SP is . A maximum set packing (MSP) is an SP of maximum size. The integer programming formulation of the MSP problem reads The MSP problem, also known in the literature as the matching problem on hypergraphs or the strong independent set problem on hypergraphs, is an NP-Hard problem. This general formulation, however, can be specialized to obtain two other famous optimization problems: the restriction of the MSP problem to sets of size 2 corresponds to the problem of maximum matching on ordinary graphs and can be solved in polynomial time [1]; the restriction where each element of appears exactly 2 times in is the maximum independent set and belongs to the NP-Hard class. The formulation ((1)–(3)) of the MSP problem, therefore, encodes an ample class of packing problems and, as all packing problems, is related by duality to a covering problem, the minimum set covering problem. Another common specialization of the general MSP problem, known as -set packing, is that in which all sets have size at most . This is one of the most studied specializations in the computer science community, the efforts concentrating on minimal degree conditions to obtain a perfect matching [2], linear relaxations [3, 4], and approximability conditions [5–7]. Motivated by this interest, we choose a -set packing problem ensemble as the principal application of the general analytical framework developed in the following sections. The asymptotic behaviour of random sparse
References
[1]
S. Micali and V. V. Vazirani, “An O algoithm for finding maximum matching in general graphs,” in Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, pp. 17–27, 1980.
[2]
N. Alon, J.-H. Kim, and J. Spencer, “Nearly perfect matchings in regular simple hypergraphs,” Israel Journal of Mathematics, vol. 100, pp. 171–187, 1997.
[3]
Z. Füredi, J. Kahn, and P. D. Seymu, “On the fractional matching polytope of a hypergraph,” Combinatorica, vol. 13, no. 2, pp. 167–180, 1993.
[4]
Y. H. Chan and L. C. Lau, “On linear and semidefinite programming relaxations for hypergraph matching,” Mathematical Programming, vol. 135, pp. 123–148, 2011.
[5]
V. R？dl and L. Thoma, “Asymptotic packing and the random greedy algorithm,” Random Structures & Algorithms, vol. 8, no. 3, pp. 161–177, 1996.
[6]
M. M. Halldórsson, “Approximations of weighted independent set and hereditary subset problems,” Journal of Graph Algorithms and Applications, vol. 4, no. 1, pp. 1–6, 2000.
[7]
E. Hazan, S. Safra, and O. Schwartz, “On the complexity of approximating K-set packing,” Computational Complexity, vol. 15, no. 1, pp. 20–39, 2006.
[8]
R. M. Karp and M. Sipser, “Maximum matchings in sparse random graphs,” in Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, vol. 12, pp. 364–375, IEEE Computer Society, 1981.
[9]
N. C. Wormald, “The differential equation method for random graph processes and greedy algorithms,” in Lectures on Approximation and Randomized Algorithms, pp. 73–155, 1999.
[10]
G. Parisi and M. Mézard, “Replicas and optimization,” Journal de Physique Lettres, vol. 46, no. 17, pp. 771–778, 1985.
[11]
G. Parisi and M. Mézard, “A replica analysis of the travelling salesman problem,” Journal de Physique, vol. 47, pp. 1285–1296, 1986.
[12]
H. Zhou and Z.-C. Ou-Yang, “Maximum matching on random graphs,” In press, http://arxiv.org/abs/cond-mat/0309348.
[13]
L. Zdeborová and M. Mézard, “The number of matchings in random graphs,” Journal of Statistical Mechanics, vol. 2006, Article ID P05003, 2006.
[14]
L. Dallasta, A. Ramezanpour, and P. Pin, “Statistical mechanics of maximal independent sets,” Physical Review E, vol. 80, Article ID 061136, 2009.
[15]
M. Mézard and M. Tarzia, “Statistical mechanics of the hitting set problem,” Physical Review E, vol. 76, no. 4, Article ID 041124, 10 pages, 2007.
[16]
M. Weigt and A. K. Hartmann, “Glassy behavior induced by geometrical frustration in a hard-core lattice-gas model,” Europhysics Letters (EPL), vol. 62, Article ID 021005, p. 533, 2003.
[17]
H. Hansen-Goos and M. Weigt, “A hard-sphere model on generalized bethe lattices: statics,” Journal of Statistical Mechanics, vol. 2005, Article ID P04006, 2005.
[18]
F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498–519, 2001.
[19]
A. Montanari and M. Mézard, Information, Physics and Computation, Oxford University Press, 2009.
[20]
G. Parisi, M. Mézard, and M. A. Virasoro, Spin Glass Theory and Beyond, World Scientific, Singapore, 1987.
[21]
M. Mézard and G. Parisi, “The cavity method at zero temperature,” Journal of Statistical Physics, vol. 22, no. 1-2, pp. 1–34, 2003.
[22]
D. Gamarnik, T. Nowicki, and G. Swirszcz, “Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method,” Random Structures and Algorithms, vol. 28, no. 1, pp. 76–106, 2006.
[23]
A. Montanari, G. Parisi, and F. Ricci-Tersenghi, “Instability of one-step replica-symmetry-broken phase in satisfiability problems,” Journal of Physics A, vol. 37, no. 6, p. 2073, 2004.
[24]
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, “Gibbs states and the set of solutions of random constraint satisfaction problems,” Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no. 25, pp. 10318–10323, 2007.
[25]
M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, “Two solutions to diluted p-spin models and XORSAT problems,” Journal of Statistical Physics, vol. 111, no. 3-4, pp. 505–533, 2002.
[26]
G. Semerjian, “On the freezing of variables in random constraint satisfaction problems,” Journal of Statistical Physics, vol. 130, no. 2, pp. 251–293, 2008.
[27]
M. Mézard and G. Parisi, “The bethe lattice spin glass revisited,” The European Physical Journal B, vol. 20, no. 2, pp. 217–233, 2001.
[28]
S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, “A new algorithm for generating all the maximal independent sets,” SIAM Journal on Computing, vol. 6, no. 3, pp. 505–517, 1977.
[29]
G. Csárdi and T. Nepusz, “The igraph software package for complex network research,” InterJournal, Complex Systems, p. 1695, 2006.
[30]
N. C. Wormald, “Models of random regular graphs,” in Surveys in Combinatorics, London Mathematical Society Lecture Note, pp. 239–298, 1999.
[31]
S. Takabe and K. Hukushima, “Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm,” In press, http://arxiv.org/abs/1301.5769.
[32]
S. Sanghavi, D. Shah, and A. S. Willsky, “Message passing for maximum weight independent set,” IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 4822–4834, 2009.
[33]
M. Weigt and H. Zhou, “Message passing for vertex covers,” Physical Review E, vol. 74, Article ID 046110, 19 pages, 2006.
