Large Independent Sets in Recursive Markov Random Graphs

• 成果类型: Article
• 署名作者: Gupte, Akshay; Zhu, Yiran
• 署名单位: University of Edinburgh; Heriot Watt University; University of Edinburgh
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0215
• 发表日期: 2025
• 关键词: chromatic number; cliques; models; bounds; limit

摘要

Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well studied for various classes of graphs. When it comes to random graphs, the classic Erdos-Renyi-Gilbert random graph G(n,p) has been analyzed and shown to have the largest independent sets of size Theta(logn) with high probability (w.h.p.) This classic model does not capture any dependency structure between edges that can appear in real-world networks. We define random graphs G(n,p)(R) whose existence of edges is determined by a Markov process that is also governed by a decay parameter r is an element of(0,1]. We prove that w.h.p. G(n,p)(R) has independent sets of size (1-r2+epsilon)nlog for arbitrary epsilon>0. This is derived using bounds on the terms of a harmonic series, a Turan bound on a stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Because G(n,p)(R) collapses to G(n,p) when there is no decay, it follows that having even the slightest bit of dependency (any r<1) in the random graph construction leads to the presence of large independent sets, and thus, our random model has a phase transition at its boundary value of r = 1. This implies that there are large matchings in the line graph of G(n,p)(R), which is a Markov random field. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most 1+log n / (1-r) w.h.p. when the lowest degree vertex is picked at each iteration and also show that, under any other permutation of vertices, the algorithm outputs a set of size Omega(n(1/1+tau)), where tau= 1/(1-r) and, hence, has a performance ratio of O(n(1/2-r)).