4
$\begingroup$

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.

It is easy to test whether $x$ is contained in all maximum-cardinality common independent sets: for this we can simply compute the size $n$ of a maximum set in $M \cap M'$ by a matroid intersection algorithm, compute the size $n'$ of a maximum set in $(M - x) \cap (M' - x)$, and test whether these have the same size. Element $x$ is in all maximum-cardinality common independent sets of $M$ and $M'$ iff $n = n'+1$.

But now consider the inclusion-wise maximal sets in $M \cap M'$, which may be smaller than a maximum common independent set. I want to determine algorithmically whether $x$ is contained in all such inclusion-wise maximal common independent sets. Clearly, a necessary condition is that $x$ is in all maximum common independent sets; but this is not sufficient. Is there a polynomial-time algorithm to determine whether $x$ is in all maximal common independent sets of two represented matroids?

I am even interested in the case that both $M$ and $M'$ are transversal matroids. Has this topic been studied before? My literature search did not turn up anything useful.

Edit: I just realized that the following question is equivalent to the one I described above: given two matroids $M$ and $M'$ and an element $x$, does one of the two matroids contain a circuit $C \supseteq {x}$ such that $C - x$ is independent in the other matroid? I'm hoping that this alternative formulation might ring a bell for someone.

$\endgroup$
2
  • $\begingroup$ How are your matroids represented? If you have them represented as a set of circuits, then there's a clear algorithm that will check your condition in time $m^2$ (where $m$ is the total number of circuits). But I believe passing from the maximal independent set representation to the circuit representation to be NP-hard... $\endgroup$ May 17, 2013 at 19:48
  • $\begingroup$ Indeed, if there is a list of circuits then the alternative formulation is easy to verify. I'm interested in the setting where $M$ and $M'$ are given by independence oracles, and (even) in the setting where $M$ and $M'$ are transversal matroids represented by 2 set systems whose partial transversals are the independent sets of the matroids. $\endgroup$ May 22, 2013 at 11:33

0

Your Answer

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