Matroid kernel

Let [math]M_1=(S,{\mathcal I}_1)[/math] and [math]M_2=(S,{\mathcal I}_2)[/math] be two matroids on the same ground set S, and let [math]\prec_1[/math] and [math]\prec_2[/math] be partial orders on S. A common independent set [math]X \in {\mathcal I}_1 \cap {\mathcal I}_2[/math] is an [math]M_1M_2[/math]-kernel if for each [math]s \in S\setminus X[/math] at least one of the following two possibilities holds:

• [math]X+s \notin {\mathcal I}_1[/math], and [math]t \preceq_1 s[/math] whenever [math]X-t+s \in {\mathcal I}_1[/math],
• [math]X+s \notin {\mathcal I}_2[/math], and [math]t \preceq_2 s[/math] whenever [math]X-t+s \in {\mathcal I}_2[/math].

Fleiner proved the following theorem.

Theorem. An [math]M_1M_2[/math]-kernel always exists, and it can be found in polynomial time using rank oracles for the matroids. In addition, a minimum cost [math]M_1M_2[/math]-kernel can be found using the ellipsoid method.