Optimal stopping for many connected components in a graph. Issue 2 (14th February 2021)

• Record Type: Journal Article
• Authors: Lasoń, Michał
• Is Part Of: Random structures & algorithms. Volume 59:Issue 2(2021)
• Page Start: 267
• Page End: 287
• Publication Date: 2021-02-14
• Subjects: connected component -- k‐tree -- optimal stopping -- tree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21000
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We study a new optimal stopping problem: Let G be a fixed graph with n vertices which become active on‐line in time, one by another, in a random order. The active part of G is the subgraph induced by the active vertices. Find a stopping algorithm that maximizes the expected number of connected components of the active part of G . We prove that if G is a k ‐tree, then there is no asymptotically better algorithm than "wait until 1 k + 1 fraction of vertices". The maximum expected number of connected components is equal to k k ( k + 1 ) k + 1 + o ( 1 ) n .