Let \(M=(E,\mathcal I)\) be a matroid with non-negative weights \(w:E\to \R_{\geq 0}\). The girth of \(M\) is \[ \min \set{\sum_{e\in C} w(e): \text{$C$ is a circuit of $M$}}. \]

Cogirth of \(M\) is the girth of the dual matroid of \(M\).

Computing girth is NP-hard for binary matroids but can be done in polynomial time for graphs. Wikipedia lists some negative complexity results, which mainly concern more general matroid classes than binary matroids. So here are some positive results filling the gap between graphic matroids and binary matroids. (Results can be found in https://matroidunion.org/?p=1106.) Proofs that you don’t see here can easily be found in the references.

1 Regular matroid

This decomposition can be found in polynomial time. One can decide if a matroid \(M\) can be decomposed into \(M_1\) and \(M_2\) using 1/2/3-sum in polynomial time. See https://www.emis.de/monographs/md/index.html.

Theorem 1 leads to a natural algorithm for computing the girth in regular matroids. The decomposition of regular matroids gives us a binary tree, where each node is a regular matroid and each leaf is either (co)graphic or a special 10 element regular matroid. Every non-leaf node in the decomposition tree represents a regular matroid \(M\) which is 1/2/3-sum of its two direct decendents \(M_1\) and \(M_2\). Let \(A \oplus_i B\) be the \(i\)-sum of \(A\) and \(B\) for \(i\in [3]\). Now there are only 3 cases:

1. \(M=M_1\oplus_1 M_2\). Direct sum does not create new circuit. \(\mathop{\mathrm{girth}}(M)=\min \set{\mathop{\mathrm{girth}}(M_1),\mathop{\mathrm{girth}}(M_2)}\).

2. \(M=M_1\oplus_2 M_2\). Let \(e\) be the common element of \(E(M_1)\) and \(E(M_2)\). In this case there may be new circuits. However, any circuit of \(M\) which is not a circuit of \(M_1\) and \(M_2\) must be contained in \(C_1\cup C_2\setminus \set{e}\), where \(C_i\) is a circuit in \(M_i\) containing \(e\). Thus to find the minimum weighted new circuit we can compute the minimum circuit in \(M_1\) containing \(e\) (say \(C_1^*\)) and replace the weight \(w(e)\) in \(M_2\) with \(w(C_1^*)-w(e)\) and then find the minimum weight circuit in \(M_2\) containing \(e\). The girth of \(M\) is the minimum among \(\mathop{\mathrm{girth}}(M_1)\), \(\mathop{\mathrm{girth}}(M_2)\) and \(\min\set{w(C): \text{$C$ is new circuit}}\).

   We need to prove that all these operations can be done in polynomial time.

   For the 2/3-sum case we need to find in at least one of the summands the minimum circuit that contains a common element \(e\). However, finding such a minimum circuit is regular matroids is not known to be polynomially solvable. To understand what’s happening here we need to look into Seymour’s proof¹ the decomposition tree.

   Instead of considering our binary decomposition tree, we now construct a new graph \(G\) where each vertex represents a graphic matroid, cographic matroid or \(R_{10}\) and there is an edge between two vertices if the corresponding matroids are patched using 1/2/3-sum. We claim that there is no cycle in the graph. The graph is connected. Assume that there is a cycle and let \(M_1,M_2\) be two matroids whose corresponding vertices are in the cycle. Consider the LCA \(M\) of \(M_1\) and \(M_2\) in the binary tree. \(M\) represents a connected subgraph \(H\subset G\) that contains \(M_1\) and \(M_2\) but not the entire cycle since otherwise there will be 2 1/2/3-sum operation between two regular matroids. However, \(M_1\) and \(M_2\) are still connected in \(G-E[H]\) since \(M_1\) and \(M_2\) are in the same cycle, which contradicts the uniqueness of the LCA.

   Thus \(G\) is a tree and we can always assume that one of the matroids in the summands is graphic matroid, cographic matroid or \(R_{10}\). Finding the minimum circuit containing a fixed element can be done in those matroids in polynomial time and there exists a algorithm that computes the tree in cubic time [2].

3. \(M=M_1\oplus_3 M_2\). Similar to the 2-sum case. There are only 3 common elements. We can enumerate all circuits of \(M_1\) which contain one of the common elements.

However, deciding whether a regular matroid has a circuit of length at most k containing two fixed elements is FPT.

2 Proper minor-closed class of binary matroids

The most important problem in this field is the following.

Similar to Seymour’s decomposition for regular matroids, every proper minor-closed class of binary matroid admits a “decomposition” into graphic matroids and some binary matroids.

The matroids \(M(A+P)\) in Theorem 3 are called perturbed graphic matroids. Note that we can consider \(k\) and \(t\) in Theorem 3 as constants since for each minor-closed class they are fixed.

Using Theorem 3, Conjecture 2 is true if one can prove the followings:

1. there is a polynomial-time alg that finds the girth of \(M(A+P)\);
2. One can reduce the problem of computing the girth of members of \(\mathcal M\) to that of computing the girth of vertically \(k\)-connected members of \(\mathcal M\).

3 Perturbed graphic matroids

Jim Geelen and Rohan Kapadia [4] showed that the (co)girth can be computed in randomized polynomial time for a subclass of binary matroids called perturbed graphic matroids. They made a reduction from the (co)girth problem of perturbed graphic matroids to graph cuts and matchings using \((s,t)\)-signed-grafts. IMO the reduction is quite tricky. Let \(s\) and \(t\) be two non-negative integers. An \((s,t)\)-signed-graft is a tuple \((G,S,T,B,C,D)\) such that:

• \(G\) is a graph,
• \(S\) is an \(s\)-element set disjoint from \(V(G)\),
• \(T\) is a \(t\)-element set disjoint from \(E(G)\),
• \(B,C,D\) are 0-1 matrices.

The incidence matrix of an \((s,t)\)-signed-graft \((G,S,T,B,C,D)\) is \[ A = \begin{array}{ccc} & \begin{array}{cc} E(G) & T \end{array} \\ \begin{array}{c} V(G) \\ S \end{array} & \left( \begin{array}{cc} A(G) & B \\ C & D \end{array} \right) \end{array} \] where \(A(G)\) is the incidence matrix of \(G\). Denote the matroid \(M(A)\) by \(M(G,S,T,B,C,D)\).

The proof is taking \(B,C\) as a rank decomposition of \(P\) and applying some row operations.

Recall that Theorem 3 says that each vertically \(k\)-connected matroid \(M\) in a proper minor-closed class of binary matroids is either \(M(A+P)\) or \(M(A+P)^*\). One has to consider the girth and cogirth problem separately.

3.1 Reductions

It follows from Lemma 4 we need to consider the (co)girth of \(M/T\) where \(M\) is the matroid of an \((s,t)\)-signed-graft.

3.2 cogirth → even cuts

By Lemma 5, to compute the cogirth of an \((s,t)\)-signed-graft we only need to consider binary matroid of the following kind:

\[ A= \begin{array}{ccc} & \begin{array}{cc} E(G) & T \end{array} \\ \begin{array}{r} V(G) \\ \set{v} \end{array} & \begin{pmatrix} A(G) & B \\ \sigma & \alpha \end{pmatrix} \end{array} \]

We want to find the cogirth of \(M(A)/T\). One useful proposition is the following. (See this post for a proof sketch.)

What we are finding is the minimum support of vectors in the row space of \(A\) such that the support has empty intersection with \(T\). Note that the support of rows in the graph incidence matrix \(A(G)\) has interpretation. They are exactly \(\delta(X)\) where \(X\) is the set of vertices for the summand rows. Thus we divide the problem into 2 cases. Let \(B[u]\) be a \(t\)-dimentional binary label on each vertex.

1. The row indexed by \(\set{v}\) is not in the solution. Find the smallest non-empty cut \(\delta(X)\) in \(G\) such that \(\sum_{u\in X}B[u]=\mathbf 0\).
2. The row indexed by \(\set{v}\) is in the solution. Now \(\sigma\) represents a subset of edges in \(G\). We want to find a cut \(\delta(X)\) such that \(\sigma \Delta \delta(X)\) is minimized and non-empty and \(\sum_{u\in X}B[u]=\alpha\).

These are called the \(t\)-dimensional even-cut problem. Geelen and Kapadia discovered a random contraction algorithm which solves both of the problems in randomized polynomial time [4].

If the graph is not connected, it is possible that \(\delta(X)\) is empty even if \(X\) is non-empty. Fortunately, Geelen and Kapadia have done the reduction to connected graphs.

Note that the size of cut \(|\delta(X)|\) is a submodular function on \(V(G)\) but \(|\delta(X)\Delta \sigma|\) is not necessarily submodular. The first case is minimizing a symmetric submodular function under some congruency constraints.

Nägele, Sudakov and Zenklusen showed that Problem 8 can be done in polynomial time if the field is small and the number of congruency constraints is constant [6].

I think currently (Sep 2025) finding a deterministic polynomial time algorithm for \(t\)-dim even cut is still open.

3.3 girth → parity cycle + parity join

Similar to the cogirth part, by Lemma 6 we consider the following matrix

\[ A= \begin{array}{ccc} & \begin{array}{cc} E(G) & \set{f} \end{array} \\ \begin{array}{r} V(G) \\ S \end{array} & \begin{pmatrix} A(G) & b \\ C & d \end{pmatrix} \end{array} \] and we want to compute the girth of \(M(A)/\set{f}\). Each edge in \(G\) has a label \(c(e)\in\F_2^{s}\) (the submatrix \(C\)). Contracting an element in a matroid may change circuits. There are two cases:

1. The minimum circuit does not contain \(\set{f}\). Then the girth of \(M(A)/\set{f}\) is the same as \(M(A)\setminus \set{f}\). In this case we need to find the minimum cycle in \(G\) such that the sum of its edge labels is exactly \(\mathbf{0}\). This is the parity cycle problem.
2. The minimum circuit contains \(\set{f}\). Let the girth of \(M(A)/\set{f}\) be \(\lambda\). Then \(M(A)\) has a minimum circuit that contains \(f\) and has size \(\lambda+1\). Let \(T\) be the set of vertices whose characteristic vector is \(b\). To find the minimum circuit of \(M(A)\), we want to find the minimum edge set \(F\subset E\) such that the sum of labels is \(d\) and \(T\) is exactly the set of vertices with odd degree in \(G[F]\). This is called the parity \(T\) join problem.

Recently, Schlotter and Sebő find FPT time algorithm for the odd \(T\)-join problem[7]. Sebő has some open problems on this topic which can be found here(page 11).

References