Optimal stopping for many connected components in a graph. Issue 2 (14th February 2021) - Lasoń, Michał
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 .