Minimum perfect bipartite matchings and spanning trees under categorization (Q1201102): Difference between revisions

Let \(G=(V,E)\) be a graph with \(E\) partitioned into \(p\) categories \(S_ 1\), \(S_ 2,\dots,S_ p\), and with each edge \(e\) having a weight \(w(e)\). Let \(D\) be a set of edges a of spanning tree of \(G\) or a set of edges a of perfect bipartite matching of \(G\). It is shown: (1) The problem of finding a spanning tree or a perfect bipartite matching, for which the value of the function \[ F(D)=\max_{1\leq i\leq p}\left\{\sum_{e\in S_ i\cap D}w(e)\right\} \] is \(\leq k\), is NP- complete on bipartite outerplanar graphs iff \(p\) is fixed at \(p=2\). (2) The problem of finding a spanning tree or a perfect bipartite matching, for which the value of the function \[ f(D)=\sum^ p_{i=1}\left\{\max_{e\in S_ i\cap D}w(e)\right\} \] is \(\leq k\), is strongly NP-complete on bipartite outerplanar graphs. (3) Minimizing \(f(D)\) can be solved in polynomial time if the number of categories is fixed, but minimizing \(F(D)\) remains NP-complete.