Power of \(k\) choices in the semi-random graph process (Q6117415)

From MaRDI portal
scientific article; zbMATH DE number 7806446
Language Label Description Also known as
English
Power of \(k\) choices in the semi-random graph process
scientific article; zbMATH DE number 7806446

    Statements

    Power of \(k\) choices in the semi-random graph process (English)
    0 references
    0 references
    0 references
    19 February 2024
    0 references
    This paper studies a generalization of the semi-randomized graph process introduced in \textit{O. Ben-Eliezer} et al. [Random Struct. Algorithms 56, No. 3, 648--675 (2020; Zbl 1442.05203)]. In this variation, the game starts with an empty graph on \(n\) vertices, and the player is presented \(k\) random vertices \(u_1,\dots,u_k\) to choose from in each round. Once a vertex \(u\) is chosen, the player then selects a vertex \(v\) and adds \(uv\) to the graph. The objective of this game is to minimize the number of rounds it takes to force the graph to satisfy some monotone graph property with high probability. In the case of \(k=1\), we have the original game. The main results come in sections 3, 4, and 5 in which the properties of minimum degree of at least \(\ell\), the existence of a perfect matching, and the existence of a Hamiltonian cycle respectively are discussed. For sections 4 and 5, an optimal algorithm was not clear, so upper and lower bounds are presented. However, in section 3 it is shown that the optimal algorithm when the property in consideration is minimum degree of at least \(\ell\) is a greedy algorithm in which the offered vertex with the lowest degree is selected and joined to a minimum-degree vertex.
    0 references
    0 references
    perfect matching
    0 references
    Hamiltonian cycle
    0 references
    semi-random graph process
    0 references

    Identifiers

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