Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
Paolo M. Camerini, Horst W. Hamacher · SIAM Journal on Discrete Mathematics · 1989
Given two matroids $M_1 = (E,\mathcal{J}_1 )$ and, $M_2 = (E,\mathcal{J}_2 )$, three algorithms for finding K best intersections $I_1 ,I_2 , \cdots ,I_K $ are presented. The first version is a straightforward application of a general procedure due to Murty and Lawler. The complexity for finding $I_2 , \cdots ,I_k $ is $O(Km^2 R(R + c(m) + \log m))$ where m is the number of elements in $E, R = \min \{ r_1 (E),r_2 (E)\} $, and $c(m)$ is the complexity of an independence oracle. By using maximum weighted border paths to compute second best intersections of modified matroids, this bound is reduced to $O(K(m^3 + mRc(m))$. Finally, a condensed version of the border graph is proposed to further improve the bound to $O(KmRc(m))$. The latter idea can also be used to find the optimal intersection $I_1 $ in $O(mR^2 c(m))$ time, which is competitive with recent matroid intersection algorithms by Frank [J. Algorithms, 2 (1981), pp. 328–336] and Brezovec, Cornuejols, and Glover [Math. Programming, 36 (1986), pp. 39–53].