Balanced problems on graphs with categorization of edges

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function: ${\displaystyle L₅\left(D\right)=\underset{1\le i\le p}{max}(\underset{e\in S_i\cap D}{max}w\left(e\right)-\underset{e\in S_i\cap D}{min}w\left(e\right))}$ For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.