Minimum perfect bipartite matchings and spanning trees under categorization

Network optimization problems under categorization arise when the edge set is partitioned into several sets and the objective function is optimized over each set in one sense, then among the sets in some other sense. Here the authors find that unlike some other problems under categorization, the minimum perfect bipartite matching and minimum spanning tree problems (under categorization) are NP-complete, even on bipartite outerplanar graphs. However for one objective function both problems can be solved in polynomial time on arbitrary graphs if the number of sets is fixed.