1
$\begingroup$

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

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.