# Is there an efficient way to compute 2-separations of matroids?

Edit: Pointers to helpful references would also be appreciated, of course.

The topic of matroids is a relatively new one for me and I don't personally know any experts of this subject. Thus, if I do not find any answers to specific questions in the literature, it is kind of hard for me to decide whether the answer is unknown or trivial (and I just don't see it). There are a lot of structural results about connectivity of matroids, cf. e.g. this paper by Oxley, but there seems to be a general lack of interest in algorithms to actually compute properties of matroids. (This may be due to matroid problems having a tendency to be NP-hard.)

I would like to have an efficient way to decide whether a connected matroid is $3$-connected, and, if it is not, to find a $2$-separation.

Background and definitions:

Let $M$ be a matroid on a (finite) ground set $E$. A partition $(X,Y)$ of $E$ is a $k$-separation of $M$ if $$\min \{ |X|, |Y| \} \ge k$$ and $$r(X) + r(Y) - r(M) < k.$$ The matroid $M$ is $k$-connected if it has no $t$-separation for any $t < k$. A $2$-connected matroid is commonly called connected.

Checking whether $M$ is connected is rather easy. Indeed, it suffices to compute a basis $B \subset E$ and its fundamental circuits $$F_B = \{ C(i,B) : i \in (E - B) \}$$ where $C(i,B)$ denotes the unique circuit contained in $B \cup \{i\}$. These fundamental circuits determine the partition of the ground set into its connected components, as two points $i,j \in E$ lie in the same component iff there is a sequence of circuits $C_1, \ldots, C_m \in F_B$ such that $i \in C_1$, $j \in C_m$ and $C_i \cap C_{i+1} \neq \emptyset$ for $i = 1, \ldots, m-1$.

This works because the connected components are equivalence classes of the relation $$i \sim j \Leftrightarrow \exists C \in \mathcal{C}(M) : i, j \in C$$ where $\mathcal{C}(M)$ denotes the set of circuits of $M$. For higher connectivity there is no such thing. I have not really thought about it, but the complexity of this procedure should be $\mathcal{O} ( |E| )$. It certainly is polynomial in $|E|$.

So – any ideas for a similar procedure to find a $2$-separation (or show that none exists)? Anything with a complexity which is polynomial in $|E|$ would be great (this problem can obviously be solved in $\mathcal{O}( 2^{|E|} )$ time).

It would also suffice to decide the existence of a vertical $2$-separation, which is a partition $(X,Y)$ of $E$ such that $$\min \{ r(X), r(Y) \} \ge k$$ and $$r(X) + r(Y) - r(M) < k.$$

• How are you given the matroid? Knuth showed that the number of sparse paving matroids of rank $n/2$ on $n$ elements is greater than $2^{\frac{1}{n} \binom{n}{n/2}} \approx 2^{n^{-3/2} 2^n}$. So simply describing such a matroid can take $\approx 2^n - (3/2) \log n$ bits! Sep 17 '13 at 13:45
• That is a good point. Ideally I'd like to be able to handle any matroid given via an independence oracle, but my main interest lies in representable matroids given via a matrix over some field.
– m_l
Sep 17 '13 at 14:04

I didn't read them carefully, but these notes of Dixby and Cunningham discuss many algorithmic questions on matroids. In particular, Chapter 6 gives an $O(n^3)$ algorithm to compute $2$-separations in a matroid on $n$ elements.