Probabilistic analysis of a sequential algorithm for finding independent sets
Tsuyoshi Kawaguchi, Hideo Nakano, Yoshiro Nakanishi · Electronics and Communications in Japan (Part I Communications) · 1982
Abstract This paper uses the constant group average degree model, which is a generalization of the constant average degree model, and evaluates the method of solution given in [1] to determine the independent vertex set. The model is a set of graphs in which there exist edges with probability pij = cicj/cn (c Σmi=1 ci|Vi|/n) independently between two vertices v and w such that v ϵ Vi and w ϵ Vj in the vertex set V = Umi=1Vi. When m = 1 holds as a special case, the model includes the constant average degree model. It is shown first that the stochastic variable BG(n, c) representing the solution by the method of [1] satisfies (1 ‐ ϵ) βG(c)n < BG (n, c) < (1 + ϵ) BG(c)n (pr.), where ϵ = 0 is sufficiently small compared with 1 and BG(c) is a value obtained by solving a recurrence formula. Then it is shown that the stochastic variable BG*(n, c) representing the size of the maximal independent set satisfies BG*(n, c) ≦ (1 + ϵ) αG(c)n (pr.), where αG(c) is a value obtained by solving an equation. The results obtained in this paper are applicable to the constant group average degree model with any |Vi| and ci.