Local algorithms for independent sets are half-optimal (Q2012245): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 05:33, 5 March 2024

scientific article
Language Label Description Also known as
English
Local algorithms for independent sets are half-optimal
scientific article

    Statements

    Local algorithms for independent sets are half-optimal (English)
    0 references
    0 references
    0 references
    28 July 2017
    0 references
    This paper considers independent sets in a random \(d\)-regular graph for large \(d\). In particular, it considers the size of independent sets that can be the output of a local algorithm that constructs independent sets. The term ``local'' refers to the assumption that the algorithm takes decisions about a vertex of the input graph based on the neighbourhood around this vertex within some bounded distance \(r\). The authors show several results about the sizes of the independent sets that can be produced by such an algorithm. Among other results, they show that such an independent set cannot be larger than \((1+ \varepsilon) d/ \log d\). Note that this is approximately half the independence number, which has been shown to be asymptotic to \(2 d /\log d\), by independent works of \textit{B. Bollobás} [Random graphs. 2nd ed. Cambridge: Cambridge University Press (2001; Zbl 0979.05003)], \textit{B. D. McKay} [Ars Comb. 23A, 179--185 (1987; Zbl 0644.05028)] as well as \textit{A. M. Frieze} and \textit{T. Łuczak} [J. Comb. Theory, Ser. B 54, No. 1, 123--132 (1992; Zbl 0771.05088)]. This result is proved through another key inequality that is also proved in the paper regarding the sizes of the intersections of such independent sets. Similar results are deduced for \(G(n,\lambda/n)\) random graphs, considering algorithms that act locally on a Galton-Watson tree whose offspring distribution is Poisson with parameter \(\lambda>0\).
    0 references
    independent set
    0 references
    local algorithm
    0 references
    random regular graphs
    0 references
    Erdős-Rényi random graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references