Online degree-bounded steiner network design

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem -- which asks for a subgraph with minimum degree that connects a given set of vertices -- is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance.