3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – David E Speyer Sep 17 '13 at 13:45
  • $\begingroup$ 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. $\endgroup$ – m_l Sep 17 '13 at 14:04
3
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is great! Exactly what I was looking for. Thank you so much! $\endgroup$ – m_l Sep 18 '13 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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