Finding Shortest Circuits in Binary Matroids

Guest Post by Rohan Kapadia. 

Two popular invariants in graph theory are the girth of graph (the size of its smallest cycle) and its edge-connectivity. Given a graph, both can be easily computed. In fact, if $e$ is an edge and $s$ and $t$ are its ends, then finding the shortest cycle or smallest edge-cut containing $e$ can be done by finding a shortest $s,t$-path or a minimum $s,t$-cut, both easy problems.

Can we generalize the problem of computing these invariants to matroids? Cycles and minimal edge-cuts in graphs correspond to circuits and cocircuits in their cycle matroids (as long as we count loops and pairs of parallel edges as cycles). So we know how to find a shortest circuit or cocircuit in a graphic matroid. Note that in the matroid world, these become just one problem, since computing the smallest size of a cocircuit is the same under duality as computing the girth of a matroid, the smallest size of a circuit.

In this post I will discuss computing the girth of a matroid. We will only consider binary matroids, since the problem is already intractable just for this class: Alexander Vardy [4] proved that it is NP-hard to compute the girth of a given binary matroid (he actually worked on an equivalent problem from coding theory, that of finding the minimum distance of a binary linear code).

But, we know that it is easy to compute the girth of two types of binary matroids, the graphic and cographic ones. Are there other subsets of the binary matroids where the problem is still tractable? The class of regular matroids is an obvious candidate to consider after the graphic and cographic. In fact, the regular matroid decomposition theorem of Paul Seymour says that any regular matroid can be built by repeated $1$-, $2$-, and $3$-sums of graphic matroids, cographic matroids, and one particular matroid called $R_{10}$. This means that for any regular matroid $M$, there is a tree $T$, each of whose vertices is either a graphic matroid, a cographic matroid, or a copy of $R_{10}$, and such that $M$ is built by $(\leq 3)$-sums from these smaller matroids, each sum corresponding to an edge of the tree. Computing the girth of regular matroids is easy if we have an algorithm to find such a tree. How to find it is beyond the scope of this post, but more information can be found in [3].

Now let’s see how to compute the girth of a regular matroid. It’s actually easier if we allow matroid elements to be weighted. If each element $e$ of a matroid $M$ has a non-negative weight $w(e)$, then we’ll say that the girth of $M$ is \[ \min\left\{\sum_{e \in C} w(e) : C \text{ is a circuit of } M\right\} . \] For graphic and cographic matroids, this introduces no difficulties since we can find minimum cuts and shortest paths even in weighted graphs.

Theorem 1. There is a polynomial-time algorithm to compute the girth of a given regular matroid $M$ with non-negative weights on its elements.

Proof. First, we need to get the tree $T$ mentioned above. If $T$ has one vertex, then $M$ is just graphic, cographic, or a copy of $R_{10}$, and the problem is easy. Otherwise, we pick any leaf of the tree, $v$. So $v$ corresponds to a matroid $M_1$ that is either graphic, cographic, or a copy of $R_{10}$. The tree $T – v$ corresponds to a regular matroid $M_2$, such that $M$ is a $(\leq 3)$-sum of $M_1$ and $M_2$. If $M$ is a $1$-sum of $M_1$ and $M_2$, then the girth of $M$ is the minimum of the girths of $M_1$ and $M_2$, so we can find it by induction.

Otherwise, suppose that $M$ is a $2$-sum of $M_1$ and $M_2$. Denote by $e$ the common element in $E(M_1)$ and $E(M_2)$. We give each element of $M_1$ and of $M_2$ the same weight as it had in $M$, and we give $e$ a weight of zero in $M_1$. We will assign the weight of $e$ in $M_2$ later. Since $M_1$ is either graphic, cographic, or a copy of $R_{10}$, we can find the following two things in polynomial time: the first is a minimum-weight circuit $C$ of $M_1 \backslash e$ and the second is a minimum-weight circuit $C’$ of $M_1$ containing $e$.

We now assign the value $\sum_{f \in C’} w(f)$ as the new weight of $e$ in $M_2$. It is not too hard to see that the girth of $M$ is the minimum of the weight of $C$ and the girth of $M_2$. We can therefore find it by induction.

The last case is when $M$ is a $3$-sum of $M_1$ and $M_2$. This is just a variant of the $2$-sum case but we need to find four circuits in $M_1$ instead of two; the details are omitted. $\square$

We have seen that computing girth is easy even in regular matroids, and the reason was that we can reduce them to graphic and cographic matroids. What about other classes of binary matroids? In an earlier entry on this blog, Peter Nelson talked about a theorem announced by Jim Geelen, Bert Gerards and Geoff Whittle [2] which gives a decomposition of binary matroids in any proper minor-closed class similar to that given by the decomposition theorem for regular matroids. The pieces in this decomposition are actually not that different from graphic and cographic matroids.

If $N$ is a binary matroid and $A$ is a matrix such that $N = M(A)$, then a rank-($\leq t$) perturbation of $N$ is a matroid of the form $M(A + T)$, where $T$ is a binary matrix with rank at most $t$.

Here is the statement of their theorem (Theorem 3.1 of [2]) from that earlier post:

Theorem 2. Let $\mathcal{M}$ be a proper minor-closed class of binary matroids. There exist integers $k$ and $t$ so that every vertically $k$-connected matroid in $\mathcal{M}$ is a rank-($\leq t$) perturbation of a graphic or cographic matroid.

This means that, for any proper minor-closed class $\mathcal{M}$ of binary matroids, we can make an efficient algorithm to compute the girth of members of $\mathcal{M}$ if we can do two things efficiently:

  1. Compute the girth of a given rank-($\leq t$) perturbation of a graphic or a cographic matroid, and
  2. 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}$.

We don’t yet know how to solve either of these two subproblems in polynomial time, though in joint work Jim Geelen and I have mostly solved the first one by finding randomized algorithms to do it, which run in polynomial time and work correctly with probability nearly 1 (I won’t say more about those algorithms in this post though).

When $\mathcal{M}$ is the class of regular matroids, Theorem 2 holds with $k = 4$ and $t = 0$ (ignoring the slight exception of $R_{10}$). We can thus compute girth in regular matroids by reducing to the easy case of graphic and cographic matroids.

Unfortunately, the trick we used to do this reduction for regular matroids does not work so easily for other classes. For regular matroids, we needed to be able to find a minimum-weight circuit in a graphic or cographic matroid that used a specified element. While this was easy, the requirement of using a specified element makes things trickier for perturbations.

In the remainder of this post, I will outline a way to compute girth only for one special type of perturbation of graphic matroids, known as the even-cut matroids. But since it’s the same problem under matroid duality, we’ll actually look at cogirth (the smallest size of a cocircuit) in the duals of even-cut matroids, which are projections of graphic matroids. A projection of a graphic matroid $M(G)$ means a matroid of the form $M(A) / e$, where $A$ is a binary matrix obtained by adding one new column, indexed by an element $e$, to the vertex-edge incidence matrix of a graph $G$. The cocircuits of this matroid are precisely the cocircuits of $M(A)$ disjoint from $e$. But we need a way to describe these cocircuits in terms of the graph $G$.

We can view the new column of $e$ that we added to the vertex-edge incidence matrix of $G$ as the characteristic vector of a set of vertices of $G$. So we can fully describe this matroid by the pair $(G, T)$ where $T$ is a subset of $V(G)$. We can assume that $|T|$ is even; if not, then $e$ is a coloop of $M(A)$ and so $M(A) / e$ is graphic and the problem becomes easy.

Now we can describe the cocircuits in terms of the graph: they are precisely the minimal edge-cutsets of the form $\delta(X)$ where $|X \cap T|$ is even. Let’s call such edge-cutsets $T$-even cuts. How can we find a minimum-size $T$-even cut and thereby compute the cogirth of this projection of a graphic matroid? Here is a solution from Barahona and Conforti [1].

Let’s say that $\delta(W)$ is a minimum $T$-even cut in the graph $G$, so we want to either find it, or find another one of equal size. We already know how to find a minimum cut in $G$ in poylnomial time, so we’ll find one of those and call it $\delta(U)$. If we are lucky and $|U \cap T|$ is even, then we’re done. Otherwise, $|U \cap T|$ is odd.

Now let’s look at the possible interactions between $W$ and $U$. Exactly one of the sets $|W \cap U \cap T|$ and $|(V(G) – W) \cap U \cap T|$ is odd and the other is even; by the symmetry between $W$ and $V(G) – W$, let’s say that $|W \cap U \cap T|$ is even. And since $|W \cap T|$ is even, the set $|W \cap (V(G) – U) \cap T|$ is also even.

That means that $\delta(W \cap U)$ and $\delta(W \cap (V(G) – U))$ are also $T$-even cuts! Unless they are empty. But they can’t both be empty, or $W$ would be empty. So suppose, by symmetry, that $\delta(W \cap U)$ is a non-empty $T$-even cut. Then we apply the submodularity inequality: \[ |\delta(W \cap U)| + |\delta(W \cup U)| \leq |\delta(U)| + |\delta(W)|. \] Since $\delta(U)$ is a minimum cut, we have $|\delta(U)| \leq |\delta(W \cup U)|$, which means that $|\delta(W \cap U)| \leq |\delta(W)|$ so $\delta(W \cap U)$ is actually a minimum $T$-even cut!

So we’ve shown that there is a minimum $T$-even cut of the form $\delta(W’)$, where $W’$ is either contained in $U$ or contained in $V(G) – U$. We construct two graphs: $G_1$ is obtained from $G$ by identifying all vertices in $U$ to a single vertex, and $G_1$ is obtained by identifying all vertices in $V(G) – U$ to a single vertex. In both cases, we add the new vertex to the set $T$. We can check that every $T$-even cut of $G_1$ or of $G_2$ is also a $T$-even cut of $G$. But in addition, our desired cut $\delta(W’)$ is definitely a $T$-even cut in either $G_1$ or $G_2$. So we finish by recursively solving the problem for these two smaller graphs.

References

[1] Francisco Barahona and Michele Conforti, A construction for binary matroids, Discrete Math. 66 (1987), 213-218.

[2] Jim Geelen, Bert Gerards and Geoff Whittle, The highly connected matroids in minor-closed classes, arXiv:1312.5012 [math.CO].

[3] K. Truemper, Matroid Decomposition, Leibniz, Plano, Texas, 1998.

[4] Alexander Vardy, The intractability of computing the minimum distance of a code, IEEE Trans. Inform. Theory 43 (1997), 1757-1766.

Leave a Reply

Your email address will not be published. Required fields are marked *