Bertrand Guenin - Matroids

I am interested in two classes of matroids, even-cycle matroids and even-cut matroids which are single element binary lifts of graphic and co-graphic matroids respectively. More specifically, I would like,

We can do (1), but (2) seems to be still out of reach (but not hopeless). Let me describe formally, (1) and indicate some of the ingredients in the algorithm. An overview of these results is available at,

What are even-cycle and even-cut matroids anyway?

By a cycle in a graph we mean a subset of the edges with the property that every vertex of the subgraph induced by these edges has even degree. An inclusion-wise minimal non-empty cycle in a graph is a circuit. A matroid is graphic if its circuits are precisely the circuits of some graph. A matroid is cographic if its circuits are precisely the inclusion-wise minimal non-empty cuts of some graph.

A signed-graph is a pair \((G,\Sigma)\) where \(G\) is a graph and \(\Sigma\subseteq EG\). A cycle \(C\) is even (resp. odd) if \(|C\cap\Sigma|\) is even (resp. odd). \(M\) is an even-cycle matroid if its circuits are precisely the inclusion-wise minimal non-empty even-cycles of some signed-graph \((G,\Sigma)\). If \(\Sigma=\emptyset\) then the even-cycles of \((G,\Sigma)\) are just the cycles of \(G\). Hence, graphic matroids are even-cycle matroids. The matrix obtained from the vertex-edge incidence matrix of \(G\) by adding a row corresponding to the characteristic vector of \(\Sigma\) is a matrix representation of \(M\) over the two-element field. In particular, even-cycle matroids are binary and are elementary lifts of graphic matroids.

A graft is a pair \((G,T)\) where \(G\) is a graph and \(T\subseteq VG\) where \(|T|\) is even. If there exists a component of \(G\) with an odd number of terminals then every cut of \((G,T)\) is defined to be even. Otherwise, a cut \(\delta(U)\) is even (resp. odd) if \(|T\cap U|\) is even (resp. odd). \(M\) is an even-cut matroid if its circuits are precisely the inclusion-wise minimal non-empty even-cuts of some graft \((G,T)\). If \(T=\emptyset\) then the even-cuts of \((G,T)\) are just the cuts of \(G\). Hence, cographic matroids are even-cut matroids. Even-cut matroids are binary and are elementary lifts of cographic matroids.

The recognition algorithms.

Tutte proved that one can recognize if a binary matroid is graphic in polynomial-time. Seymour extended this result and showed that there exists a polynomial time algorithm to check if a matroid specified by an independence oracle is graphic. Thus given a binary matroid described by its 0,1 matrix representation we can check in polynomial time if the matroid is graphic and we can check in polynomial time if the matroid is cographic. We prove the corresponding results for even-cycle matroids and even-cut matroids, namely,

By “polynomial time”, we mean polynomial in the number of entries of the matrix representation. We believe that these algorithms ought to be fast in practice but have not conducted numerical experiments.

Why is this problem hard?

For this discussion I will focus on even-cycle matroids but analogous results hold for even-cut matroids. Given a graphic matroid \(M\) we say that \(G\) is a graphic representation of \(M\) if the circuits of \(G\) correspond to the circuits of \(M\). Consider a graph \(G\) with a two vertex cutset. If \(G'\) is obtained from \(G\) by flipping the subgraph on one side of the \(2\)-separation as indicated in the following figure then \(G'\) is a 2-flip of \(G\). We call a 1-flip the identification of two vertices in distinct components or splitting two blocks into different components. Two graphs are equivalent if they are related by a sequence of \(1\)-flips and \(2\)-flips. Given a graphic matroid \(M\) where the circuits of \(M\) correspond to the circuits of a graph \(G\) we say that \(G\) is a graph representation of \(M\).

Theorem

Any two graphic representations of a graphic matroid are equivalent.

A signed-graph \((G,\Sigma)\) is a signed-graph representation of an even-cycle matroid \(M\) if the cycles of \(M\) are precisely the even-cycles of \((G,\Sigma)\). If \((G,\Sigma)\) is a signed-graph representation of an even-cycle matroid \(M\) then so is \((G’,\Sigma’)\) where \(G'\) is equivalent to \(G\) and \(\Sigma’=\Sigma\triangle\delta(U)\) for some cut \(\delta(U)\) where \(\triangle\) denotes the symmetric difference of two sets. We say that \((G,\Sigma)\) and \((G’,\Sigma’)\) are equivalent in that case as well.

Is there an analogue of Whitney's result for even-cycle matroids? Alas no, indeed we have the following,

Remark

An even-cycle matroid may have an exponential number of pairwise inequivalent signed-graph representations.

This bad behaviour arises for degenerate instances of even-cycle matroids. Let us formalize this. We say that an even-cycle matroid is pinch-graphic if it has a signed-graph representation with a blocking pair i.e. a pair of vertices that intersects every odd circuit. Pinch-graphic matroids generalize graphic matroids but form a proper subclass of even-cycle matroids. We indicate in the following venn diagram the relation between these classes of matroids.

Theorem

There exists a constant \(c\) such that every even-cycle matroid that is not pinch-graphic has fewer than \(c\) pairwise inequivalent signed-graph representations.

We show in the following paper that if we have polynomial algorithm to recognize pinch graphic matroids then we can use it to recognize in polynomial time both even-cycle and even-cut matroids.

But what to do about pinch-graphic matroids

Of course we still need to know how to recognize pinch-graphic matroids. Here connectivity helps, namely,

Theorem

Let \(M\) be a pinch-graphic matroid that is not graphic. If \(M\) is internally \(4\)-connected then the number of signed-graph representations with a blocking pair is polynomial.

We then show that this allows you to check if an internally \(4\)-connected matroid is pinch-graphic, see

The last piece of the puzzle is how to handle matroids that are not internally \(4\)-connected. We prove structure theorems for separations of order at most three in pinch-graphic matroids and leveraging these, we give an algorithm that takes as input an arbitrary binary matroid \(M\) (described by its 0,1 matrix representation) and either certifies that \(M\) is pinch-graphic, or certifies that \(M\) is not pinch-graphic, or finds a proper minor \(N\) of \(M\) that is internally \(4\)-connected where \(N\) is pinch-graphic if and only if \(M\) is. We then can use our previous algorithm to check whether \(N\) is pinch-graphic. This work can be found in,