Matroid 3-connectivity algorithm

This past week I worked on the first thing in the GSOC proposal–the 3-connectivity algorithm for matroids. (full proposal here)

A matroid is 3-connected if there is no partition of the groundset E into E_1 and E_2 such that |E_1|,|E_2|\geq 2 and r(E_1)+r(E_2)=r(E)+1, where r is the rank function.

Bixby and Cunningham[1] found a recursive characterization of 3-connectivity, which lead to an efficient recursive algorithm. (I recommend this survey to go with the work)

  1. Verify if the matroid is simple, cosimple and connected. If not, then either it’s one of the five 3-connected matroids with size at most 3 or it is not 3-connected.
  2. If the rank of the matroid is 2, return true.
  3. Pick a basis B. Find a fundamental cocircuit Y such that deleting it gives us a disconnected matroid. If none exist, return true.
  4. Otherwise, one have to check a certain graph related to the components of M\setminus Y is connected.
    • If it is, intuitively (details are messy) we apply the 3-connectivity algorithm to each component.
    • Otherwise, the matroid is not 3-connected.

One can show the bottleneck of the algorithm is in the second step, where we try to test the connectivity of M\setminus Y, which is known to take O(r(E)|E|) time. Bixby and Cunningham has proved we only have to find connectivity of at most r(E) matroids if we pick the basis carefully. Hence the running time is O(r^2(E) |E|).

The new implementation is much faster than the previous one. The constants hidden in the big-Oh is small, and it’s fast even on small inputs. The plan for this week is implementing an alternative algorithm for 3-connectivity called shifting. It also works for higher connectivity.

I like to thank my mentors Stefan van Zwam and Michael Welsh who have been holding weekly meetings with me. I also like to thank Rudi Pendavingh, who has offered detailed suggestions and sometimes implemented the optimization himself. :)

[1] R.E Bixby, W.H Cunningham. Matroids, graphs and 3-connectivity, J.A Bondy, U.S.R Murty (Eds.), Graph Theory and Related Topics, Academic Press, New York (1979), pp. 91–103

Matroid 3-connectivity algorithm

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s