# 3 Matroid Intersection, a Special Case

It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.

Question: Does this problem remain NP-Hard if one of the matroids is a partition matroid with only two sets in the partition*? (no restrictions on the other matroids).

*By "two sets in the partition" I mean that this partition matroid is a matroid $$(E,I)$$ such that there is a partition $$E_1,E_2$$ of $$E$$ and bounds $$c_1,c_2 \in \mathbb{N}$$ such that $$I = \{ S \subseteq E~|~ |S \cap E_1| \leq c_1, |S \cap E_2| \leq c_2 \}$$.

Your problem is a multi-budgeted matroid intersection with two budgets. There is a PTAS for that [1]. However, your case is so special, better algorithm exists.

You can assume there is only a single budget by truncating the rank of one of the other 2 matroids to $$c_1+c_2$$. Also, the weights are 0-1 weights. Observe the problem is equivalent to the following problem.

Given matroid $$M_1$$ and $$M_2$$ and $$R, c$$, find a common independent set $$B$$ of $$M_1$$ and $$M_2$$, such that $$|R\cap B|\leq c$$ and $$|B|$$ is maximized.

The above problem can be solved in polynomial time. One can reduce it to a sequence of maximum weighted matroid intersection. Indeed, we give each element outside of $$R$$ a weight of $$1$$, and elements in $$R$$ has weight $$\epsilon << 1$$, and look for a maximum weight common independent set of $$M_1$$ and $$M_2$$. This will try to find a common independent set $$B$$ such that $$|B|$$ is maximized, and under that constraint, $$R$$ is minimized. However, it is possible that $$|R\cap B|>c$$, therefore we can truncate the matroid $$M_1$$ to a matroid with one fewer rank, and repeat the process. We truncate $$M_1$$ repeatedly until eventually we obtain $$|R\cap B|\leq c$$. $$B$$ would be the desired common independent set.

I have no idea what to do if you want maximum weight common independent set while requiring $$|R\cap B|\leq C$$.

[1] Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico, Multi-budgeted matchings and matroid intersection via dependent rounding, Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1080-1097 (2011). ZBL1377.90071.

• Indeed, this shows that the problem is not APX-hard. What about NP-Hardness?
– John
Apr 13, 2023 at 10:42
• I made an update. If you just want a maximum cardinality common independent set, then it is solvable in polynomial time. Apr 13, 2023 at 16:37