论文标题
递归马尔可夫随机图中的大型独立集
Large independent sets in recursive Markov random graphs
论文作者
论文摘要
计算图中独立集合的最大大小是一个著名的硬组合问题，对各种图表进行了充分研究。当涉及到随机图时，已经对经典的erdős-rényi-gilbert随机图$ g_ {n，p} $进行了分析，并证明具有最大的独立集合$θ（\ log {n}）$ w.h.p.该经典模型不会捕获可在现实世界网络中出现的边缘之间的任何依赖性结构。我们通过定义随机图来启动研究$ g^{r} _ {n，p} $，其边缘的存在由马尔可夫进程确定，该过程也由decay参数$ r \ in（0,1] $。我们证明W.H.P. $(\frac{1-r}{2+ε}) \frac{n}{\log{n}}$ for arbitrary $ε> 0$, which implies an asymptotic lower bound of $Ω(π(n))$ where $π(n)$ is the prime-counting function. This is derived using bounds on the terms of a harmonic series, Turán bound on stability number, and a一定依赖的依赖性变量的一定序列的浓度分析也可能具有独立的兴趣。 $ r = 1 $。对于贪婪算法，我们的性能比率最多为$ 1 + \ frac {\ frac {\ log {n}} {（1-r）} $w.h.p。 $ω（n^{1/1+τ}）$，其中$τ= 1/（1-r）$，因此具有$ O（n^{\ frac {1} {2-r}}）$ O的性能比。
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, only the classical Erdős-Rényi-Gilbert random graph $G_{n,p}$ has been analysed and shown to have largest independent sets of size $Θ(\log{n})$ w.h.p. This classical model does not capture any dependency structure between edges that can appear in real-world networks. We initiate study in this direction by defining random graphs $G^{r}_{n,p}$ whose existence of edges is determined by a Markov process that is also governed by a decay parameter $r\in(0,1]$. We prove that w.h.p. $G^{r}_{n,p}$ has independent sets of size $(\frac{1-r}{2+ε}) \frac{n}{\log{n}}$ for arbitrary $ε> 0$, which implies an asymptotic lower bound of $Ω(π(n))$ where $π(n)$ is the prime-counting function. This is derived using bounds on the terms of a harmonic series, Turán bound on stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Since $G^{r}_{n,p}$ 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$. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most $1 + \frac{\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 $Ω(n^{1/1+τ})$, where $τ=1/(1-r)$, and hence has a performance ratio of $O(n^{\frac{1}{2-r}})$.
