The optimal path-matching problem (Q1272178)

Let \(T_1\), \(T_2\) be two disjoint stable sets in the vertex set \(V\) of a graph \(G\) and let \(V-(T_1 \cup T_2)\) be \(R\). If \(M_1, M_2\) are matroids on \(T_1\) and on \(T_2\), respectively, with the common rank \(r\) then a basic path-matching is defined as a collection of \(r\) vertex disjoint paths, all of whose internal vertices are in \(R\), linking a basis of \(M_1\) to a basis of \(M_2\), together with a perfect matching of the vertices of \(R\) not in any of the paths. This concept is a common generalization of the perfect matching (put \(R=V\)) and the common basis of two matroids (put \(R=\varnothing\) and let \(G\) be a perfect matching joining copies \(T_1, T_2\) of a set \(T\)). The authors give polynomial-time solvability, min-max theorems, totally dual integral polyhedral description, strongly polynomial separation algorithms for the convex hull of matchable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.