The Complexity of Bottleneck Labeled Graph Problems

摘要

We study bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as an s-t path, a spanning tree, or a perfect matching) while trying to minimize the maximum (or, alternatively, maximize the minimum) number of edges picked from any given color.