Online promise problems with online width metrics

摘要

In this article we consider the application of ideas from parameterized complexity, and topological graph theory, to online problems. We focus on parameterized promise problems, where we are promised that the problem input obeys certain properties, or is presented in a certain fashion.We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed input to instances having some form of bounded treewidth or pathwidth.We also consider the effects of restricting the presentation of the input to some form of bounded width decomposition or layout. A consequence of this part of the work is the clarification of a new parameter for graphs, persistence, which arises naturally in the online setting, and is of interest in its own right. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions.