Refael Hassin
email: hassin@post.tau.ac.il.

Jérôme Monnot
email: monnot@lamsade.dauphine.fr.

Danny Segev
email: segevd@post.tau.ac.il.

The complexity of Bottleneck Labeled Graph Problems

Keywords: Bottleneck labeled problems, approximation algorithms, hardness of approximation, s-t path, s-t cut, spanning tree, perfect matching

In the present paper, 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 that of being an s-t path, a spanning tree, or a perfect matching) while trying to avoid over-picking or under-picking edges from any given color.

Introduction

Let G = (V, E) be a directed or undirected graph, with a weight function w : E → R + and a labeling function L : E → {c 1 , . . . , c q }. We interchangeably refer to the elements of L(E) as labels or colors. In addition, for E ′ ⊆ E and 1 ≤ i ≤ q, we use L i (E ′ ) = {e ∈ E ′ : L(e) = c i } to denote the collection of c i -colored edges in E ′ . With this notation in mind, the c i -color weight of an edge set E ′ ⊆ E is defined as e∈L i (E ′ ) w(e), i.e., the total weight of all c i -colored edges in E ′ . Now let P be a given graph property defined on subsets of E, such as that of inducing a spanning tree, an s-t path, an s-t cut, or a perfect matching. The min-max weighted labeled P problem (henceforth, WL-min-max P) asks to compute an edge set E ′ ⊆ E satisfying P that minimizes max i e∈L i (E ′ ) w(e), the maximum color weight of E ′ . Similarly, in max-min weighted labeled P (WL-max-min P), the minimum color weight should be maximized. We refer to both versions as weighted labeled bottleneck P problems. Furthermore, for ease of presentation, we denote by UL-min-max P the unweighted special case of WL-min-max P, that asks to minimize the maximum color frequency. Analogous notation will also be used for the corresponding max-min variant.

The complexity of WL-min-max P has been investigated for several graph properties by Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF], Punnen [START_REF] Punnen | Traveling salesman problem under categorization[END_REF][START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF], and Averbakh and Berman [START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF], in the context of "optimization problems under categorization". As indicated in [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF], WL-min-max P contains both min-max weighted P and min-sum weighted P as special cases. One simply has to assign a distinct label to each edge in the former variant, and a single label for all edges in the latter variant. Similar arguments lead to an analogous result, stating that max-sum weighted P can be formulated in terms of WL-max-min P. Consequently, whenever min-sum weighted (respectively, max-sum weighted) P is NP-hard, so is WL-min-max (respectively, max-min) P.

Our results

We now provide, for each problem considered in this paper, a brief description of our main findings, accompanied by a concise summary of previous work.

Labeled bottleneck s-t path

Previous work:

1. Averbakh and Berman [START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF] showed that WL-min-max s-t path is weakly NP-hard, even in bicolored graphs. Moreover, they proved that UL-min-max s-t path is NP-hard for an arbitrary number of colors. These results apply to both directed and undirected graphs.

2. In [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [GT54], p. 203), it was mentioned that the pair-choice vertex problem is NP-hard. Here, we are given a directed graph G = (V, E), two specified nodes {s, t} ⊆ V , and a collection of pairwise-disjoint pairs of arcs. The objective is to determine whether there exists an s-t path traversing at most one arc from any given pair. Since UL-min-max directed s-t path can be viewed as a special case of this problem (pairs correspond to colors), the former cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP.

3. It is not difficult to verify that UL-max-min s-t path generalizes the longest path problem, even in monochromatic graphs. Therefore, the results of Karger, Motwani and Ramkumar [START_REF] Karger | On approximating the longest path in a graph[END_REF]Thm. 11] imply that UL-max-min s-t path cannot be approximated within a factor of 2 O(log 1-ǫ n) for any fixed ǫ > 0, unless NP ⊆ DTIME(2 O(log 1/ǫ n) ).

New results:

1. UL-max-min s-t path is not approximable at all, unless P=NP (Theorem 4.1).

2. For a fixed number of colors, there is a fully polynomial-time approximation scheme for WL-min-max s-t path (Corollary 3.2).

3.

For an arbitrary number of colors, there is a polynomial-time algorithm that constructs a feasible solution to UL-min-max s-t path in undirected graphs using O( √ nOPT) edges from any given color. Here, n = |V | and OPT denotes the objective value of an optimal solution (Subsection 4.2). For directed graphs, the path we construct traverses O( √ mOPT) edges from any color, where m = |E| (Subsection 4.3).

Labeled bottleneck spanning tree

Previous work: Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF] showed that WL-min-max spanning tree is weakly NP-hard, even in bicolored graphs. We are not aware of previous work regarding the max-min version of this problem.

New results:

1. WL-min-max spanning tree is strongly NP-hard (Corollary 5.2); it can be approximated within a factor of O(log n) (Subsection 5.3).

2. UL-min-max spanning tree can be solved in polynomial time (Theorem 5.4).

3. UL-max-min spanning tree can be solved in polynomial time (Theorem 5.3). WL-maxmin spanning tree is strongly NP-hard (Corollary 5.2), and it is also weakly NP-hard in planar bicolored graphs (Theorem 2.1).

4. For a fixed number of colors, there is a fully polynomial-time approximation scheme for both versions of weighted labeled bottleneck spanning tree (Corollary 3.2).

Labeled bottleneck perfect matching

Previous work:

1. Richey and Punnen [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF] showed that WL-min-max perfect matching is weakly NP-hard, even in bicolored graphs. A stronger result has recently been obtained by Punnen [START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF], who proved that even the simpler WL-min-max assignment problem is strongly NPhard.

2. Itai, Rodeh, and Tanimoto [START_REF] Itai | Some matching problems for bipartite graphs[END_REF] proved that the following problem is NP-complete: Given a bipartite graph and a collection of pairs of edges, decide whether there exists a perfect matching that picks at most one edge from any given pair. This problem remains NP-complete for a collection of disjoint pairs [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [GT59], p. 203).

Since UL-min-max perfect matching can be viewed as a special case of this problem, the former cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP.

3. Karzanov [START_REF] Karzanov | Maximum matchings of given weight in complete and complete bipartite graphs[END_REF], and Yi, Murty and Spera [START_REF] Yi | Matchings colored networks[END_REF] proved that, given a complete bipartite graph K n,n with edges colored either red or blue, the problem of finding a perfect matching consisting of exactly r red edges and nr blue edges is polynomial-time solvable 1 . Therefore, UL-min-max and UL-max-min perfect matching in complete bipartite bicolored graphs can be solved to optimality in polynomial time.

4. To our knowledge, WL-max-min perfect matching has not been studied in the literature.

New results:

1. WL-max-min perfect matching is weakly NP-hard in bicolored planar graphs (Theorem 2.1). UL-max-min perfect matching is not approximable at all in general graphs, unless P=NP (Theorem 6.1).

2.

There is an approximation-preserving reduction from UL-min-max directed s-t path to UL-min-max perfect matching (Theorem 6.2).

3. For a fixed number of colors, there is a fully polynomial-time approximation scheme for both versions of weighted labeled bottleneck perfect matching (Corollary 3.2).

Labeled bottleneck s-t cut

Previous work: To our knowledge, both versions of this problem have not been studied yet.

New results:

1. UL-min-max s-t cut is NP-hard in bicolored graphs (Theorem 2.3). When the underlying graph is planar, UL-min-max s-t cut cannot be approximated within a factor of 2ǫ for any fixed ǫ > 0, unless P=NP (Theorem 7.1), and the weighted version of this problem is weakly NP-hard when the graph is bicolored as well (Theorem 2.1).

2. WL-max-min s-t cut is weakly NP-hard in planar bicolored graphs (Theorem 2.1).

For an arbitrary number of colors, this problem is not approximable at all in planar multigraphs, unless P=NP (Theorem 7.2).

Related work

In this section, we provide a brief survey of several frameworks to which our contributions are related. Since some of the settings under consideration have received a great deal of attention in recent years, it is beyond the scope of this writing to present an exhaustive overview. We refer the reader to the undermentioned papers and to the references therein for a more comprehensive review of the literature.

Multiobjective combinatorial optimization [START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF][START_REF] Gandibleux | Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey[END_REF][START_REF] Ulungu | Multi-objective combinatorial optimization problems: A survey[END_REF][START_REF] White | A bibliography on the applications of mathematical programming multipleobjective methods[END_REF]. The basic ingredients of a multiobjective optimization problem are typically: A set of instances I; a set of feasible solutions F(x) associated with every instance x ∈ I; and a collection of cost functions w 1 (x, y), . . . , w k (x, y) associated with every instance x ∈ I and feasible solution y ∈ F(x).

Given an instance x ∈ I, the goal is to solve min y∈F (x) {w 1 (x, y), . . . , w k (x, y)}, where the exact meaning of "min" depends on the particular setting in question. For example, it may stand for Pareto optimality (see Section 3), for aiming to minimize the worst cost function, or for lexicographically minimizing the vector of cost functions. It is not difficult to verify that WL-min-max P is actually a multiobjective optimization problem in disguise: The set of feasible solutions consists of all edge sets that satisfy P; for every color c i there is a corresponding cost function w i which is exactly the c i -color weight; and the goal is to minimize the maximum cost function. Minor adjustments allow us to treat WL-max-min P in a similar way.

Robust discrete optimization [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF][START_REF] Bertsimas | Robust discrete optimization and network flows[END_REF][START_REF] Dhamdhere | How to pay, come what may: Approximation algorithms for demand-robust covering problems[END_REF]. Very informally, robust optimization deals with decision making in environments of considerable data uncertainty, trying to come up with solutions that hedge against the worst contingency that may arise. Several alternative approaches for coping with uncertainty have been explored and exploited; however, the scenario-based framework of Kouvelis and Yu [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF] seems most relevant to our paper. In this context, future developments are described by a finite number of scenarios, each of which corresponds to a possible realization of the unknown model parameters. The objective is to optimize against the worst possible scenario by using a min-max objective. Once again, we note that WL-min-max P can be easily cast as a scenario-based robust optimization problem: For every color c i there is an analogous scenario s i , in which the weight w s i (e) of an edge e ∈ E is set to w(e) if its color is c i , and to 0 otherwise. In addition, the cost of an edge set E ′ ⊆ E in scenario s i is given by e∈E ′ w s i (e), which is exactly the c i -color weight of this set.

The min-sum-max setting. A complementary line of work [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF][START_REF] Punnen | On bottleneck assignment problems under categorization[END_REF] on edge-colored graphs attempts to minimize the sum of the maximal edge weight picked from every given color. In particular, when all edges are associated with unit weights, a problem of this nature reduces to that of constructing subgraphs satisfying a required property while minimizing the number of colors used. Some properties that have recently been studied in this context include spanning trees [START_REF] Chang | The minimum labeling spanning trees[END_REF][START_REF] Broersma | Spanning trees with many or few colors in edge-colored graphs[END_REF][START_REF] Brüggemann | Local search for the minimum label spanning tree problem with bounded color classes[END_REF][START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF], s-t paths [START_REF] Broersma | Paths and cycles in colored graphs[END_REF][START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF], and perfect matchings [START_REF] Monnot | The labeled perfect matching in bipartite graphs[END_REF].

2 Fixed Number of Colors: Hardness Results

Weak NP-hardness in bicolored graphs

In what follows, we prove that several weighted labeled bottleneck problems are NP-hard, even in planar bicolored graphs. As indicated in Subsection 1.1, WL-min-max P is known to be NP-hard in bicolored graphs [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF][START_REF] Averbakh | Categorized bottleneck-minisum path problems on networks[END_REF] for P ∈ {spanning tree, s-t path, perfect matching}.

Theorem 2.1. WL-min-max P and WL-max-min P are NP-hard, even in planar bicolored graphs, for P ∈ {s-t path, s-t cut, perfect matching, spanning tree}.

Proof. We propose a reduction from the partition problem, whose instances consist of a collection of integers {a 1 , . . . , a n }, and the goal is to decide whether or not there exists a subset J ⊆ {1, . . . , n} such that j∈J a j = j / ∈J a j . To this end, for every 1 ≤ i ≤ n consider a 4-edge cycle on the set of vertices {x i , l i , y i , r i }, listed clockwise, with edge colors

L(x i , l i ) = L(y i , r i ) = c 1 , L(x i , r i ) = L(y i , l i ) = c 2 ,
and weights w(x i , l i ) = w(x i , r i ) = a i , w(y i , l i ) = w(y i , r i ) = 0. These n cycles describe a graph H ′ . For the perfect matching case, we define H = H ′ . For the s-t path and spanning tree cases, we construct H from H ′ by identifying y i and x i+1 to a single vertex (for every 1 ≤ i ≤ n -1), and setting s = x 1 , t = y n . Finally, for the s-t cut case, we construct H from H ′ by deleting the vertex y i along with the edges (y i , r i ) and (y i , l i ) in each 4-cycle, and identifying r 1 , . . . , r n to a vertex s, and l 1 , . . . , l n to t.

In each of these cases, it is easy to verify that the resulting WL-min-max P instance has an objective value of at most 1 2 n j=1 a j if and only if there exists J ⊆ {1, . . . , n} with j∈J a j = j / ∈J a j . Similarly, WL-max-min P has an objective value of at least 1 2 n j=1 a j , for P ∈ {s-t path, s-t cut, perfect matching}. Regarding WL-max-min spanning tree, some edge weights need to be changed: We set w(y i , l i ) = w(y i , r i ) = n j=1 a j , for every 1 ≤ i ≤ n. Consequently, the latter problem has an objective value of at least (n + 1 2 ) n j=1 a j if and only if there exists J ⊆ {1, . . . , n} with j∈J a j = j / ∈J a j .

Strong NP-hardness for s-t cuts

Aissi, Bazgan and Vanderpooten [START_REF] Aissi | Pseudo-polynomial algorithms for min-max and min-max regret problems[END_REF] proved that min-max robust P with a fixed number of scenarios admits pseudo-polynomial algorithms for s-t paths and spanning trees in general graphs and for perfect matchings in planar graphs. Since WL-min-max P can be viewed as a special case of these settings (see Subsection 1.2), it follows that the corresponding min-max labeled problems have pseudo-polynomial algorithms for a fixed number of colors.

In contrast, we proceed by proving that WL-min-max s-t cut is strongly NP-hard in bicolored graphs. A similar result was established for bi-criteria s-t cut [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF]Thm. 6], and more recently for min-max robust s-t cut with two scenarios [START_REF] Aissi | Complexity of the min-max (regret) versions of cut problems[END_REF]Cor. 1]. Unfortunately, in their reductions the resulting instances do not correspond to WL-min-max s-t cut instances, and it appears as if we cannot conclude the result for WL-min-max s-t cut in an obvious way. However, we can slightly modify the construction of Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF].

Theorem 2.2. WL-min-max s-t cut is strongly NP-hard in bicolored graphs.

Proof. We propose a reduction from the bisection width problem. Given a connected graph

G = (V, E) on 2n vertices, a bisection is a cut (V 1 , V 2 ) of G with |V 1 | = |V 2 | = n.
The decision version of bisection width asks to determine, for a given integer k, whether there exists a bisection with at most k edges. This problem is known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [ND17], p. 210).

Given an instance of bisection width, as described above, we construct an instance I = (G ′ , w, L) of WL-min-max s-t cut, with G ′ = (V ′ , E ′ ) and L(E ′ ) = {c 1 , c 2 }, as follows:

• G ′ has two additional vertices, s and t, each of which is connected to every vertex of G.

• L(s, v) = c 1 for every v ∈ V ; all other edges have color c 2 .

• w(s, v) = k(n + 1) and w(t, v) = kn for every v ∈ V ; w(e) = n for every original edge e ∈ E.

We now argue that G has a bisection of size at most k if and only if I has an s-t cut whose min-max value is at most kn

(n + 1). If (V 1 , V 2 ) is a bisection with at most k edges, then ({s} ∪ V 1 , {t} ∪ V 2 ) is an s-t cut in G ′ that picks c 1 -colored edges of total weight e∈({s},V 2 ) w(e) = kn(n + 1) and c 2 -colored edges of total weight e∈({t},V 1 ) w(e) + e∈(V 1 ,V 2 ) w(e) = kn 2 + kn = kn(n + 1). Conversely, let ({s} ∪ V 1 , {t} ∪ V 2 )
be an s-t cut in G ′ with min-max value of at most kn(n + 1). Since each c 1 -colored edge of this cut has a weight of k(n + 1), it follows that |V 2 | ≤ n. In addition, the c 2 -colored edges of this cut have a total weight of n|E ′′ | + kn|V 1 |, where E ′′ = (V 1 , V 2 ), and we conclude that

|V 1 | ≤ n + 1. Now, if |V 1 | = n + 1 the inequality n|E ′′ | + kn|V 1 | ≤ kn(n + 1) implies E ′′ = ∅, so G is clearly disconnected (contradicting our initial assumption); thus |V 1 | ≤ n. Finally, since |V 1 | ≤ n and |V 2 | ≤ n, we have |V 1 | = |V 2 | = n, and therefore (V 1 , V 2 ) is a bisection with at most k edges.
Theorem 2.3. UL-min-max s-t cut is NP-hard in bicolored graphs.

Proof. To prove the theorem, we show that a ρ-approximation for UL-min-max s-t cut can be converted in polynomial time into a ρ-approximation for WL-min-max s-t cut when the edge weights are integers upper bounded by a polynomial in n. The theorem follows from the combination of this result and Theorem 2.2.

Let I = (G, w, L) be an instance of WL-min-max s-t cut, where G = (V, E) has n vertices and max e∈E w(e) = O(n O (1) ). We replace each edge e = (u, v) ∈ E by a collection H(e) of w(e) edge-disjoint paths of length two (connecting u and v), each edge of which is colored by L(e). The vertices u and v will be called extreme vertices of H(e), whereas other vertices of H(e) will be called inner vertices. We refer to the resulting UL-min-max s-t cut instance as

I ′ = (G ′ , L ′ ).
Consider an s-t cut (S ′ , T ′ ) in G ′ , with s ∈ S ′ and t ∈ T ′ . We iteratively apply the following procedure for each original edge e ∈ E: If the extreme vertices of H(e) appear in the same set of the partition, assign all inner vertices of H(e) to that set. These changes can only decrease the total weight of L(e)-colored edges in the current s-t cut, and therefore also its min-max value. From the resulting s-t cut (S ′ , T ′ ), we can find an s-t cut in G of identical min-max value by considering (S ′ ∩ V, T ′ ∩ V ), the restriction of this cut to G.

Fixed Number of Colors: An FPTAS

In what follows, we present a fully polynomial-time approximation scheme for weighted labeled bottleneck s-t path, spanning tree, and perfect matching, for a fixed number of colors.

Approximate Pareto curves

Let P be a property described in Section 1, and consider the multiobjective version of P (henceforth, Multi k P). An instance I of this problem consists of a graph G = (V, E), and a weight vector w(e) = (w 1 (e), . . . , w k (e)) for each edge e ∈ E. An edge set E ′ ⊆ E forms a feasible solution to Multi k P if it satisfies P, and the objective value of E ′ is given by the vector ( e∈E ′ w 1 (e), . . . , e∈E ′ w k (e)). In a minimization problem, we say that a solution E ′ is dominated by E ′′ if e∈E ′′ w i (e) ≤ e∈E ′ w i (e) for every 1 ≤ i ≤ k, and the inequality is strict for at least one index; the inequalities are reversed for a maximization problem. The goal is to compute the Pareto curve C(I), which is the set of all undominated solutions to I. Finally, an ǫ-approximate Pareto curve for the minimization (respectively, maximization) version of Multi k P is a set C ǫ (I) of solutions such that 1. |C ǫ (I)| is polynomially bounded in terms of the input size and 1 ǫ . 2. For every E * ∈ C(I), there exists

E ′ ∈ C ǫ (I) with e∈E ′ w i (e) ≤ (1 + ǫ) e∈E * w i (e)
for every 1

≤ i ≤ k (respectively, e∈E ′ w i (e) ≥ (1 -ǫ) e∈E * w i (e)).
When k is fixed, Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF]Cor. 5] proposed an FPTAS for constructing ǫ-approximate Pareto curves of multiobjective s-t walk, spanning tree, and perfect matching.

The approximation scheme

We now relate the approximability of several weighted labeled bottleneck problems to that of their multiobjective counterparts. This approach has already been suggested in the context of robust optimization [START_REF] Kouvelis | Robust Discrete Optimization and its Applications[END_REF][START_REF] Aissi | Approximation complexity of min-max (regret) versions of shortest path, spanning tree, and knapsack[END_REF], implying that results similar to those described in the next theorem can be immediately derived for the min-max variants.

Theorem 3.1. For a fixed number of colors, the efficient construction of an ǫ-approximate Pareto curve for the maximization version of Multi k P implies a (1-ǫ)-approximation to WLmax-min P. A similar result for the minimization version leads to a (1 + ǫ)-approximation to WL-min-max P.

Proof. For purposes of brevity, we deal with the maximization setting, noting that the arguments below can be easily adapted to the corresponding minimization problem. Let I = (G, L, w) be an instance of WL-max-min P such that L(E) = {c 1 , . . . , c k }. We construct an instance I ′ = (G, w ′ ) of Multi k P, where the weight vector w ′ (e) = (w ′ 1 (e), . . . , w ′ k (e)) associated with each edge e ∈ E is defined by setting w ′ i (e) = w(e) if L(e) = c i , and w ′ i (e) = 0 otherwise. As a result, the objective vector of a feasible solution E ′ to I ′ is given by ( e∈L 1 (E ′ ) w(e), . . . , e∈L k (E ′ ) w(e)).

Now let E * be an optimal solution to the instance I of WL-max-min P, with an objective value of OPT(I); if this instance does not have a unique optimal solution, E * is picked so that k i=1 e∈L i (E * ) w(e) is maximized. Clearly, the Pareto curve C(I ′ ) contains E * . Now, consider an ǫ-approximate Pareto curve C ǫ (I ′ ) for the maximization version of Multi k P. We pick a solution E ′ ∈ C ǫ (I ′ ) maximizing min i e∈E ′ w i (e) as a solution for WL-max-min P; since C ǫ (I ′ ) can be constructed and enumerated in polynomial time, so is our algorithm. Moreover, by definition of C ǫ (I ′ ), since E * ∈ C(I ′ ) there exists

E ′′ ∈ C ǫ (I ′ ) satisfying e∈E ′′ w i (e) ≥ (1 -ǫ) e∈E * w i (e) for every 1 ≤ i ≤ k. Hence, we conclude that E ′ constitutes a (1 -ǫ)-approximation to I, since min 1≤i≤k e∈L i (E ′ )
w(e) ≥ min

1≤i≤k e∈L i (E ′′ )
w(e) ≥ (1ǫ)

e∈L i (E * )
w(e) = (1ǫ)OPT(I) .

By combining Theorem 3.1 and the results of Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] mentioned earlier, Corollary 3.2 follows. However, an important remark is in place. Even though the algorithm in [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] constructs an ǫ-approximate Pareto curve of multiobjective s-t walk, note that any such walk can be converted (by eliminating cycles) to an s-t path of no greater min-max objective value. An analogous claim regarding the max-min version is incorrect. Corollary 3.2. For a fixed number of colors, weighted labeled bottleneck spanning tree and perfect matching admit a fully polynomial-time approximation scheme. A similar result also holds for WL-min-max s-t path.

Arbitrary Number of Colors: Labeled Bottleneck s-t Paths

For a fixed number of colors, UL-min-max s-t path is polynomial time solvable. This claim follows from the observation that we can decide whether there exists a walk connecting s and t whose objective value is exactly p ∈ {1, . . . , n -1} by means of dynamic programming. In contrast, we proceed by showing that both versions of the problem under consideration become NP-hard for an arbitrary number of colors. We complement these results by devising efficient approximation algorithms.

Hardness results

We now derive new inapproximability bounds for both versions of labeled bottleneck s-t path, in undirected as well as directed graphs. To our knowledge, these results do not follow from existing work. Theorem 4.1. UL-min-max s-t path is not (2-ǫ)-approximable for any fixed ǫ > 0, and ULmax-min s-t path is not approximable at all, unless P=NP. Similar results hold for directed graphs.

Proof. oncoming reductions will be based on the set packing and set covering Given a family of sets S = {S 1 , . . . , S m } over a ground set X = {x 1 , . . . , x n } and an integer k, the objective of the set packing problem is to decide whether S contains at least k pairwisedisjoint sets. The set covering problem asks whether X can be covered by at most k sets in S. Both set packing and set covering are known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problems [SP3] and [SP5], p. 221-222).

Given (S, X), we create an instance I = (G, L) of unweighted labeled bottleneck s-t path, where L has n colors {c 1 , . . . , c n }. For each set S i = {x i 1 , . . . , x ip } we define a distinct path H(S i ) consisting of p edges, each given a unique color from {c i 1 , . . . , c ip }. Now, the graph = (V, E) is constructed in the following way:

• Create a path of length k on the vertices v 1 , . . . , v k+1 , in left-to-right order.

• Replace each edge (v j , v j+1 ) by m paths connecting v j and v j+1 ; for every 1 ≤ i ≤ m, the i-th path is a copy of H(S i ).

• Finally, set s = v 1 and t = v k+1 .

It is not difficult to verify that the objective value of the UL-min-max s-t path instance I is at most 1 if and only if there exists a set packing of size at least k. In addition, the objective value of the UL-max-min s-t path instance I at least 1 if and only if there exists a set covering of size at most k. Thus, we conclude that it is NP-complete to distinguish between OPT(I) = 1 and OPT(I) ≥ 2 for UL-min-max s-t path, and also between OPT(I) = 0 and OPT(I) ≥ 1 for UL-max-min s-t path.

UL-min-max s-t path: Approximating the undirected case

In what follows, we show how to efficiently construct an undirected s-t path using O( √ nOPT) edges from any given color, where n = |V | and OPT denotes the cost of an optimal solution. An essential building block of our algorithm is a constant-factor approximation for multibudget maximum coverage. An instance of this problem consists of a ground set U and collection of subsets S ⊆ 2 U , which is partitioned into {S 1 , . . . , S r }. Given an integral budget b t for each part S t , the objective is to find a subcollection S ′ ⊆ S such that S ′ picks at most b t sets from each S t and such that the number of elements covered by S ′ is maximized. For these particular settings, a performance guarantee of 1 -1 e be achieved by adopting the maximum coverage heuristic of Ageev and Sviridenko [1, Rem. 2].

The algorithm. For simplicity of presentation, it would be convenient to assume that OPT is known in advance. Clearly, this assumption can be enforced by testing 1, . . . , n -1 as candidate values, and returning the best solution found. We also make use of ∆ = ∆(n, OPT) as a parameter whose value will be determined later.

1. F ← ∅, H ← G.
2. While dist H (s, t) > ∆ (a) Create a multi-budget maximum coverage instance by: The ground set is V (H);

for each edge e ∈ E(H) there is a corresponding subset V e , consisting of the endpoints of e; these subsets are partitioned into {S 1 , . . . , S q }, where S i = {V e : L(e) = c i }; each S i has a budget of OPT.

Approximate the instance defined above, and let F + be the collection of edges e ∈ E(H) for which V e is picked by the resulting solution.

(c) F ← F ∪ F + , H ← the contraction of F + in H.

3.

Let P be a shortest s-t path in H. Return F ∪ P . Proof. We begin by showing that, for any value of ∆, step 2 terminates within no more than 4n ∆ iterations. For this purpose, it is sufficient to prove that the number of vertices in H decreases by at least ∆ 4 whenever an edge set is contracted. Let E * ⊆ E be an optimal solution, with max i |L i (E * )| = OPT, and consider a single iteration. Since the edges E * ∩ E(H) form a subgraph of H containing an s-t it follows that {V e : e ∈ E * ∩ E(H)} is a feasible solution to the multi-budget maximum coverage instance defined in step 2a. Moreover, as the s-t distance in H is at least ∆, the latter solution satisfies

| e∈E * ∩E(H) V e | ≥ ∆. Consequently, for the current F + we must have | e∈F + V e | ≥ (1 -1
e )∆, implying that the contraction of F + decreases the number of vertices by at least 1 2 (1 -1 e )∆ > ∆ 4 . Now, starting with an empty set of edges, in each iteration of step 2 we augment F with an edge set F + that contains at most OPT edges from each color. Therefore, by setting ∆ = √ nOPT, the maximum number of edges we pick from any given color is at most

4n ∆ OPT + |P | ≤ 4n ∆ OPT + ∆ = 5 √ nOPT .
4.3 UL-min-max s-t path: Approximating the directed case

In the following, we demonstrate that ideas similar to those presented in Subsection 4.2 can be employed to construct a directed s-t path using O( √ mOPT) arcs from any given color. Here, m = |E| and OPT denotes the cost of an optimal solution.

The algorithm. Once again, we assume that OPT is known in advance, and let ∆ = ∆(m, OPT) be a parameter whose value will be determined later.

1. F ← ∅, χ E\F ← characteristic function of E \ F .
2. While dist χ E\F (s, t) > ∆ (a) Create a multi-budget maximum coverage instance by: The ground set is V ; for each arc e = (u, v) ∈ E \ F there is a corresponding singleton V e = {v}; these subsets are partitioned into {S 1 , . . . , S q }, where S i = {V e : L(e) = c i }; each S i has a budget of OPT.

(b) Approximate the instance defined above, and let F + be the collection of arcs e ∈ E \ F for which V e is picked the resulting solution.

(c) F ← F ∪ F + .

3. Let P be a shortest s-t (with respect to χ E\F ). Return P . Proof. We first demonstrate that step 2 consists of at most 2m ∆ iterations, by showing that we always have |F + | ≥ ∆ 2 . Let P * be an optimal solution, with max i |L i (P * )| = OPT. In each iteration, {V e : e ∈ P * \ F } is a feasible solution to the multi-budget maximum coverage instance defined in step 2a. Moreover, as dist χ E\F (s, t) > ∆, the latter solution satisfies

| e∈P * \F V e | ≥ ∆. Consequently, we must have |F + | ≥ | e∈F + V e | ≥ (1 -1 e )∆ > ∆ 2
. Now, starting with an empty set of arcs, in each iteration of step 2 we augment F with an arc set F + that contains at most OPT arcs from each color. Therefore, by setting ∆ = √ mOPT, the maximum number of edges P traverses from any given color is at most

|F | + ∆ ≤ 2m ∆ OPT + ∆ ≤ 3 √ mOPT .

Arbitrary Number of Colors: Labeled Bottleneck Spanning Trees

In Corollary 3.2 we have shown that, for a fixed number of colors, both versions of weighted labeled spanning tree admit an FPTAS. In this section, we provide hardness results, exact algorithms, and approximation algorithms for the general case of an arbitrary number of colors.

Hardness results

As indicated in Subsection 1.1, WL-min-max spanning tree is known to be weakly NP-hard [START_REF] Richey | Minimum perfect bipartite matchings and spanning trees under categorization[END_REF]. Here, we show that both weighted labeled bottleneck spanning tree problems are in fact strongly NP-hard.

Theorem 5.1. Both weighted labeled bottleneck spanning tree problems are strongly NP-hard in multigraphs.

Proof. We propose a reduction from 3-partition. The input to this problem consists of a collection of integers {a 1 , . . . , a 3m }, satisfying σ 4 < a i < σ 2 , where σ = 1 m 3m i=1 a i . The objective is to decide whether there is a partition of {1, . . . , 3m} into sets S 1 , . . . , S m with i∈S j a i = σ for every 1 ≤ j ≤ m. The 3-partition problem is known to be strongly NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [SP15], p. 224).

Let {a 1 , . . . , a 3m } be an instance of 3-partition. We construct an instance I = (G, w, L) for both weighted labeled bottleneck spanning tree versions, where L(E) = {c 1 , . . . , c m } and G is a graph on set of vertices u, v 1 , . . . , v 3m . For every 1 ≤ i ≤ 3m, there are m parallel edges connecting u to v i ; each of these edges is given a distinct color in {c 1 , . . . , c m } and its weight is set to a i .

The claim follows from the observation that there is a 3-partition of {a 1 , . . . , a 3m } if and only if the optimal value of the WL-min-max (respectively, max-min) spanning tree instance is at most σ (respectively, at least σ).

Corollary 5.2. Both weighted labeled bottleneck spanning tree problems are strongly NP-hard in simple graphs.

Proof. We show how to transform the multigraph defined in the proof of Theorem 5.1 into a simple graph. For this purpose, for every 1 ≤ i ≤ 3m we split the vertex v i into v i,1 , . . . , v i,m (thereby creating a unique copy for each parallel edge connecting u to v i ), add a new vertex v i,m+1 , and add the edges (v i,1 , v i,2 ), . . . , (v i,m , v i,m+1 ). For every 1 ≤ j ≤ m, the color of (v i,j , v i,j+1 ) is set to c j , but its weight depends on the problem in question. For WL-min-max spanning tree, w(v i,j , v i,j+1 ) = 0, whereas for the max-min version w(v i,j , v i,j+1 ) = mσ. In the former case, the conclusion is identical to that of the original proof. In the latter case, there is a 3-partition of {a 1 , . . . , a 3m } and only if the optimal value of the WL-max-min spanning tree instance is at least (3m 2 + 1)σ.

Exact algorithms

Broersma and Li [START_REF] Broersma | Spanning trees with many or few colors in edge-colored graphs[END_REF] devised a polynomial-time algorithm based on matroid intersection for computing a spanning tree using a maximum number of colors. Here, we prove that both unweighted labeled bottleneck spanning tree problems can also be solved in polynomial time by utilizing matroid intersection. It is interesting to observe that this result is in contrast to the weighted case, which was shown to be strongly NP-hard in Corollary 5.2.

Theorem 5.3. UL-max-min spanning tree can be solved to optimality in polynomial time.

Proof. Given an instance (G, L) of UL-max-min spanning tree, with G = (V, E), we may assume without loss of generality that OPT is known in advance, since we can test 0, . . . , n-1 as candidate values for this parameter, and return the best solution found. Now, since the optimal tree picks at least OPT edges from every color in L(E) = {c 1 , . . . , c q }, it follows that there exists a forest picking exactly OPT edges from any given color. Moreover, such a forest can be efficiently constructed by computing a maximum cardinality intersection 2 of the matroids M 1 and M 2 , where

• M 1 = (E, I 1 ) is the graphic matroid, that is, I 1 = {F ⊆ E : F is a forest}. 2 See, for example, [START_REF] Lawler | Combinatorial Optimization: Networks and Matroids[END_REF]Chap. 8].

• M 2 = (E, I 2 ) is a partition matroid, with

I 2 = {F ⊆ E : |L i (F )| ≤ OPT for every 1 ≤ i ≤ q}.
We complete the resulting forest into a spanning tree in an arbitrary way, noting that this augmentation leaves the objective value unchanged.

Theorem 5.4. UL-min-max spanning tree can be solved to optimality in polynomial time.

Proof. The algorithm for this version is nearly identical to the one given for UL-maxmin spanning tree; however, an important remark is in place. After we "guess" OPT and compute a maximum cardinality intersection F ⊆ E of M 1 and M 2 , there is no need to complete the subgraph induced by F into a spanning tree, implying that its objective value remains unchanged. This claim follows from observing that |F | = |V | -1, since the edge set of the optimal spanning tree forms a feasible solution to the matroid intersection problem we solve.

WL-min-max spanning tree: A logarithmic approximation

In what follows, we show that a matroid intersection algorithm is not only a useful tool for solving the unweighted version to optimality; rather, it can also be applied to approximate the weighted min-max version.

The algorithm. For ease of exposition, we assume without loss of generality that an estimator of the optimum W ∈ [OPT, 2 • OPT] is known in advance. Otherwise, for every 0 ≤ k ≤ ⌈log nwmax w min ⌉, we can test 2 k w min a candidate value and return the best solution found, where w min and w max denote the minimum and maximum non-zero edge weights, respectively.

1. Delete all edges of weight greater than W , and define a partition of the undeleted edges as follows:

(a) For every 1 ≤ i ≤ q and 0 ≤ k ≤ ⌊log n⌋, let E i,k be the set of edges e with L(e) = c i and w(e) ∈ ( W 2 k+1 , W 2 k ]. In addition, let E free be the set of remaining edges (of weight at most W n ).

2. By applying a matroid intersection algorithm, find a spanning tree T that picks at most 2 k+1 edges from each E i,k and any number of edges from E free . Return T .

Note that the suggested algorithm is well-defined. To establish this claim, it is sufficient to show that a spanning tree satisfying the constraints of step 2 indeed exists. It is easy to verify that all edges of the optimal tree T * survive step 1 and that |T * ∩ E i,k | ≤ 2 k+1 , or otherwise there is a color c i from which T * picks edges of total weight strictly greater than W ≥ OPT.

Theorem 5.5. The edges picked by T from any given color have an overall weight of at most (4⌊log n⌋ + 6)OPT.

Proof. Consider some color c i . Then,

e∈L i (T ) w(e) = ⌊log n⌋ k=0 e∈T ∩E i,k w(e) + e∈L i (T ∩E free ) w(e) ≤ ⌊log n⌋ k=0 |T ∩ E i,k | • max e∈T ∩E i,k w(e) + |T ∩ E free | • max e∈T ∩E free w(e) ≤ ⌊log n⌋ k=0 2 k+1 W 2 k + (n -1) W n ≤ (2⌊log n⌋ + 3)W ≤ (4⌊log n⌋ + 6)OPT .
The second inequality holds since |T ∩ E i,k | ≤ 2 k+1 for every 0 ≤ k ≤ ⌊log n⌋, and since |T ∩ E free | ≤ n -1. The last inequality follows from the assumption W ≤ 2 • OPT.

Arbitrary of Colors: Labeled Bottleneck Perfect Matchings

In Theorem 2.1 we proved that both versions of weighted labeled bottleneck perfect matching are NP-hard in bicolored graphs. In this section, we provide hardness approximation results.

Theorem 6.1. UL-max-min perfect matching is not approximable at all, unless P=NP, even in planar bipartite graphs.

Proof. We describe a reduction from (3, B2)-SAT. An instance (C, X) of this problem consists of a collection C = (C 1 , . . . , C m ) of m clauses of size exactly 3 over the set X = {x 1 , . . . , x n } of boolean variables, such that every variable occurs exactly twice positively and twice negatively. The objective is to decide whether there exists a truth assignment that satisfies all clauses. This problem was shown to be NP-complete by Berman, Karpinski and Scott [6, Thm. 1].

Given an instance I = (C, X) of (3, B2)-SAT, as described above, we construct an instance I ′ = (G, L) of UL-max-min perfect matching, where = (V, E) is a collection of n vertexdisjoint cycles of length 4 and L(E) = {c 1 , . . . , c m }: 1. Each variable x i has its own cycle of length 4, to which we refer as H(x i ).

2. Now let {C j 1 , C j 2 } ⊆ C be the clauses in which x i appears in positive form, and {C j 3 , C j 4 } ⊆ C be those in which it appears in negative form. Then, the edges of H(x i ) are colored by c j 1 , c j 3 , c j 2 , c j 4 (clockwise).

This construction guarantees that the edges with colors corresponding to clauses containing the literal x i form a matching in H(x i ), and so do the edges corresponding to clauses containing xi . the original instance I is satisfiable if and only if there exists a perfect matching M in G using each color at least once. We conclude that it is NP-hard to distinguish between UL-max-min perfect matching instances of objective values 0 and 1.

We now present an approximation-preserving reduction from UL-min-max directed s-t path to UL-min-max perfect matching. By combining this result with Theorem 4.1, we derive new inapproximability results for the latter problem. Theorem 6.2. UL-min-max perfect matching is not (2-ǫ)-approximable for any fixed ǫ > 0, unless P=NP, even in bipartite graphs.

Proof. Since Theorem 4.1 establishes, for any fixed ǫ > 0, a lower bound of 2ǫ on the approximability of UL-min-max directed s-t path, it is sufficient to show that a ρapproximation for this problem will be implied by the existence of a ρ-approximation for UL-min-max perfect matching in bipartite graphs.

Given an instance I = (G, s, t, L) of UL-min-max directed s-t path, we transform it into an instance I = (G ′ , L ′ ) of UL-min-max perfect matching, where G ′ is an undirected bipartite graph. The latter is created by splitting each vertex v ∈ V \ {s, t} to v in and v out followed by adding the edge (v in , v out We also cancel the orientation, and replace each arc by a corresponding edge of identical color. Finally, each new edge of the form (v in , v out ) is given a unique color, c ′ v . We first claim that OPT(I ′ ) ≤ OPT(I). To this end, consider a directed path s = v 1 , v 2 , . . . , v k = t constitutes an optimal solution to I. Then, by picking the union of {(v i out , v i+1 in ) : 1 ≤ i ≤ k -1} and {(v in , v out ) : v ∈ V \ {v 1 , . . . v k }} we obtain a perfect matching in G ′ whose objective value is exactly OPT(I). Consequently, it remains to show that, given a perfect matching M in G ′ , we can efficiently find a directed s-t path in G whose objective value does not exceed that of M The reduction described above guarantees that there exists a collection of vertices V M ⊆ V such that M consists of an edge set {(v in , v out ) : v ∈ V M } and an edge set {(u out , v in ) : u, v ∈ V \ V M }. It is not difficult to verify that the latter set induces a directed s-t path in G (and quite possibly one or more directed cycles). The objective value of this path is upper bounded by that of M .

7 Arbitrary Number of Colors: Labeled Bottleneck s-t Cuts 2.2, we proved that WL-min-max s-t cut is strongly NP-hard. However, careful examination reveals that the instances resulting from our reduction are not necessarily planar. Since the maximum s-t cut problem is polynomially solvable in planar graphs [START_REF] Orlova | Finding the maximum cut in a graph[END_REF][START_REF] Hadlock | Finding a maximum cut of a planar graph in polynomial time[END_REF], it is of interest to show that the former problem remains computationally intractable in such graphs. We also provide new inapproximability results for UL-max-min s-t cut.

Theorem 7.1. UL-min-max s-t cut is not (2ǫ)-approximable in planar graphs for any fixed ǫ > 0, unless P=NP.

Proof. We propose a reduction from the set packing problem, whose definition is given in Theorem 4.1. Let I = (S, X, k) be a set packing instance, where S = {S 1 , . . . , S m } is a family of sets over a ground set X = {x 1 , . . . , x n }. We define an instance of UL-min-max s-t cut, consisting of a planar graph G = (V, E) whose edges are given colors from the set {c 0 , c 1 , . . . , c n }. The graph is initially a collection of k interior-disjoint paths 1 , . . . , P k connecting s to t, each of length m. Then, for each path P i we perform the following modification: For every 1 ≤ j ≤ m, the j-th edge e j = (x, y) of P i is replaced by a collection of |S j | interior-disjoint paths of length 2 connecting x to y; letting S j = {x j 1 , . . . , x jp }, we spread the colors {c j 1 , . . . , c jp } the first edges of these |S j | paths, and set the color of their second edges to c 0 . The theorem follows from the observation that I has a set packing of size at least k if and only if the objective value of the newly defined UL-min-max cut instance is at most 1.

Theorem 7.2. UL-max-min s-t cut is not approximable at all in planar multigraphs, unless P=NP.

Proof. We describe a reduction from the satisfiability problem, whose instances consist of a collection C = (C 1 , . . . , C m ) of clauses over a set X = {x 1 , . . . , x n } of boolean variables. The goal is to decide whether there is a truth assignment that satisfies all clauses. This problem is known to be NP-complete [START_REF] Garey | Intractability: A Guide to the Theory of NP-Completeness[END_REF] (problem [LO1], p. 259).

We construct an instance of UL-max-min s-t cut, where G = (V, E) and L(E) = {c 1 , . . , c m }. The set of vertices is V = {s, t, v 1 , . . . , v n }, and there are n i (respectively, ni ) parallel edges joining s (respectively, t) and v i , where n i (respectively, ni ) is the number of x i (respectively, xi ) occurrences. Finally, the colors of these edges are given by the clauses containing x i (respectively, xi ). It is not difficult to verify that I is satisfiable if and only if there exists an s-t cut in G whose objective value is at least 1.

Theorem 4 . 2 .

 42 By setting ∆ = √ nOPT, the subgraph induced by F ∪ P picks at most 5 √ nOPT edges from any given color.

Theorem 4 . 3 .

 43 By setting ∆ = √ mOPT, the directed path P traverses at most 3 √ mOPT arcs from any given color.

On the other hand, the complexity of this problem in general bipartite graphs is still open.

Acknowledgments. We thank Shlomi Rubinstein for suggesting the reduction in Theorem 4.1, which simplified our original proof.