Bertrand Guenin  MatroidsI am interested in two classes of matroids, evencycle matroids and evencut matroids which are single element binary lifts of graphic and cographic 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 evencycle and evencut 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 inclusionwise minimal nonempty 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 inclusionwise minimal nonempty cuts of some graph. A signedgraph 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 evencycle matroid if its circuits are precisely the inclusionwise minimal nonempty evencycles of some signedgraph \((G,\Sigma)\). If \(\Sigma=\emptyset\) then the evencycles of \((G,\Sigma)\) are just the cycles of \(G\). Hence, graphic matroids are evencycle matroids. The matrix obtained from the vertexedge incidence matrix of \(G\) by adding a row corresponding to the characteristic vector of \(\Sigma\) is a matrix representation of \(M\) over the twoelement field. In particular, evencycle 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 evencut matroid if its circuits are precisely the inclusionwise minimal nonempty evencuts of some graft \((G,T)\). If \(T=\emptyset\) then the evencuts of \((G,T)\) are just the cuts of \(G\). Hence, cographic matroids are evencut matroids. Evencut 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 polynomialtime. 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 evencycle matroids and evencut 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 evencycle matroids but analogous results hold for evencut 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 2flip of \(G\). We call a 1flip 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\). In 1933 Whitney proved that, Theorem
Any two graphic representations of a graphic matroid are equivalent. This result explains why it is relatively easy to recognize graphic matroids. A signedgraph \((G,\Sigma)\) is a signedgraph representation of an evencycle matroid \(M\) if the cycles of \(M\) are precisely the evencycles of \((G,\Sigma)\). If \((G,\Sigma)\) is a signedgraph representation of an evencycle 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 evencycle matroids? Alas no, indeed we have the following, Remark
An evencycle matroid may have an exponential number of pairwise inequivalent signedgraph representations. This bad behaviour arises for degenerate instances of evencycle matroids. Let us formalize this. We say that an evencycle matroid is pinchgraphic if it has a signedgraph representation with a blocking pair i.e. a pair of vertices that intersects every odd circuit. Pinchgraphic matroids generalize graphic matroids but form a proper subclass of evencycle matroids. We indicate in the following venn diagram the relation between these classes of matroids. In contrast to the previous remark we have that, Theorem
There exists a constant \(c\) such that every evencycle matroid that is not pinchgraphic has fewer than \(c\) pairwise inequivalent signedgraph 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 evencycle and evencut matroids.
But what to do about pinchgraphic matroidsOf course we still need to know how to recognize pinchgraphic matroids. Here connectivity helps, namely, Theorem
Let \(M\) be a pinchgraphic matroid that is not graphic. If \(M\) is internally \(4\)connected then the number of signedgraph representations with a blocking pair is polynomial. We then show that this allows you to check if an internally \(4\)connected matroid is pinchgraphic, 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 pinchgraphic 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 pinchgraphic, or certifies that \(M\) is not pinchgraphic, or finds a proper minor \(N\) of \(M\) that is internally \(4\)connected where \(N\) is pinchgraphic if and only if \(M\) is. We then can use our previous algorithm to check whether \(N\) is pinchgraphic. This work can be found in,
