sage2015gsocmatroid

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)

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.
If the rank of the matroid is 2, return true.
Pick a basis $B$ . Find a fundamental cocircuit $Y$ such that deleting it gives us a disconnected matroid. If none exist, return true.
Otherwise, one have to check a certain graph related to the components of 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