notesum.ai

Published at December 3

cs.DS

Released Date: December 3, 2024

Authors: Ilan Doron-Arad¹, Ariel Kulik¹, Hadas Shachnai¹

Aff.: ¹Technion, Haifa, Israel

Exact (red blue) Matroid Intersection (EMI)
Instance	$(E,R,{\mathcal{I}}_{1},{\mathcal{I}}_{2},k)$ : matroids $(E,{\mathcal{I}}_{1}),(E,{\mathcal{I}}_{2})$ , red elements $R\subseteq E$ , and $k\in{\mathbb{N}}$ .
Objective	Decide if there is a common basis $B$ for the two matroids such that $\|B\cap R\|=k$ .