<p>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.</p>
<p>You can assume there is only a single budget by truncating the rank of one of the other 2 matroids to <span class="math-container">$c_1+c_2$</span>. Also, the weights are 0-1 weights. Observe the problem is equivalent to the following problem.</p>
<blockquote>
<p>Given matroid <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span> and <span class="math-container">$R, c$</span>, find a common independent
set <span class="math-container">$B$</span> of <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span>, such that <span class="math-container">$|R\cap B|\leq c$</span> and <span class="math-container">$|B|$</span> is maximized.</p>
</blockquote>
<p>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 <span class="math-container">$R$</span> a weight of <span class="math-container">$1$</span>, and elements in <span class="math-container">$R$</span> has weight <span class="math-container">$\epsilon &lt;&lt; 1$</span>, and look for a maximum weight common independent set of <span class="math-container">$M_1$</span> and <span class="math-container">$M_2$</span>. This will try to find a common independent set <span class="math-container">$B$</span> such that <span class="math-container">$|B|$</span> is maximized, and under that constraint, <span class="math-container">$R$</span> is minimized. However, it is possible that <span class="math-container">$|R\cap B|&gt;c$</span>, therefore we can truncate the matroid <span class="math-container">$M_1$</span> to a matroid with one fewer rank, and repeat the process. We truncate <span class="math-container">$M_1$</span> repeatedly until eventually we obtain <span class="math-container">$|R\cap B|\leq c$</span>. <span class="math-container">$B$</span> would be the desired common independent set.</p>
<p>I have no idea what to do if you want maximum weight common independent set while requiring <span class="math-container">$|R\cap B|\leq C$</span>.</p>
<p>[1] <em>Chekuri, Chandra; Vondrák, Jan; Zenklusen, Rico</em>, <a href="http://dl.acm.org/citation.cfm?id=2133118" rel="nofollow noreferrer"><strong>Multi-budgeted matchings and matroid intersection via dependent rounding</strong></a>, 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). <a href="https://zbmath.org/?q=an:1377.90071" rel="nofollow noreferrer">ZBL1377.90071</a>.</p>

CC BY-SA 4.0
2023-04-13T10:42:24.367Z
Indeed, this shows that the problem is not APX-hard. What about NP-Hardness?
John
CC BY-SA 4.0
2023-04-13T16:37:33.003Z
I made an update. If you just want a maximum cardinality common independent set, then it is solvable in polynomial time.
Chao Xu
CC BY-SA 4.0
2023-04-09T00:55:56.960Z
2023-04-13T16:36:52.023Z
2023-04-13T16:36:52.023Z
Chao Xu
<p>It is well known that finding a maximum cardinality (or weight) common independent set in the intersection of 3 matroids is APX-Hard.</p>
<p><strong>Question:</strong> 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).</p>
<p>*By &quot;two sets in the partition&quot; I mean that this partition matroid is a matroid <span class="math-container">$(E,I)$</span> such that there is a partition <span class="math-container">$E_1,E_2$</span> of <span class="math-container">$E$</span> and bounds <span class="math-container">$c_1,c_2 \in \mathbb{N}$</span> such that <span class="math-container">$I = \{ S \subseteq E~|~ |S \cap E_1| \leq c_1, |S \cap E_2| \leq c_2 \}$</span>.</p>

<np-hardness><approximation-algorithms><approximation-hardness><partition-problem><matroids>
3 Matroid Intersection, a Special Case
John
# 3 Matroid Intersection, a Special Case

(Asked by: username_0 on 2023-04-08)

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 \}$.

**Tags:** np-hardness, approximation-algorithms, approximation-hardness, partition-problem, matroids


---

## 1 answers

### Answer by username_1 on 2023-04-09. Score: 4

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**](http://dl.acm.org/citation.cfm?id=2133118), 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](https://zbmath.org/?q=an:1377.90071).

> **Comments:**
> **username_0**: Indeed, this shows that the problem is not APX-hard. What about NP-Hardness?  
> **username_1**: I made an update. If you just want a maximum cardinality common independent set, then it is solvable in polynomial time.  

---

