Biased graphs and their matroids III

Here I am again, discussing frame and lift matroids. As in my previous post, I’ll denote by $FM(\Omega)$ and $LM(\Omega)$ respectively the frame and lift matroid of $\Omega$.

Following on Jim Geelen’s post on framework matroids, I’ll discuss recognition algorithms (or lack thereof) for some classes of lift and frame matroids. Jim’s post starts with Seymour’s beautiful theorem (in [S81], Theorem 1 in Jim’s post) which, for a given matroid $M$ and graph $G$, allows one to check whether $M=M(G)$ in polynomial time. In [G92], del Greco proved the following analogue to Seymour’s theorem for frame matroids. (In the next theorem, the star of a vertex $v$ is the set of edges incident with $v$ which are not balanced loops.)

Theorem 1: Let M be a matroid and let $\Omega=(G,\mathcal{C})$ be a biased graph where $G$ is connected and has at least two vertices. Then $M=FM(\Omega)$ if and only if the following hold:

1. the star of every vertex of $G$ is a union of cocircuits of $M$,
2. every vertex-disjoint union of unbalanced cycles of $\Omega$ is not a circuit of $M$,
3. no balanced cycle of $\Omega$ is properly contained in a circuit of $M$, and
4. $r(M)\leq r(FM(\Omega))$.

Unfortunately, this theorem doesn’t lead to a polynomial time algorithm for checking if $M=FM(\Omega)$, since the number of cycles in a graph may be exponential in the number of edges. This seems to support Conjectures 1 and 2 in Jim’s post.

One may hope that the recognition algorithm problem may be more tractable when turning our attention to specific classes of frame and lift matroids. Alas, even for the well behaved class of bicircular matroids, a polynomial-time recognition algorithm does not exist, unless $P=NP$. In fact it is shown in [CCW85] that it is NP-hard to determine whether a matroid $M$ is bicircular, even if $M$ is representable and a matrix representation is given. I couldn’t actually get hold of this reference, but a strengthening of this result may be found in [CGW93]. This paper also contains a polynomial-time algorithm to determine whether a matroid (given as an independence set oracle) is the bicircular matroid of a graph that belongs to a certain family of graphs.

Rudi Pendavingh and Stefan van Zwam have devised a recognition algorithm for a special class of signed-graphic matroids. This is the class of sixth-roots-of-unity graphic matroids, i.e. matroids representable by a sixth-roots-of-unity matrix with at most two nonzero entries per column. This corresponds to the class of signed graphs with no $-K_4$- and no $\pm K_3$-minor (where $-K_4$ is $K_4$ with all cycles unbalanced and $\pm K_3$ is a $K_3$ with all edges doubled, where every pair of parallel edges forms an unbalanced cycle). Musitelli’s algorithm for recognizing binet matrices  [M07] “almost” works for the whole class of signed-graphic matroids. That is, given a real matrix representation of a matroid $M$, Musitelli’s algorithm would recognize if $M$ is signed graphic as long as the columns of the matrix have already been scaled correctly, so only row operations are needed to get a matrix with two nonzeroes entries per column (these entries being $\pm 1$).

Aside from graphic matroids, I don’t know of any other polynomial-time recognition algorithm for classes of frame matroids. The situation is just as bad for lift matroids. This lack of algorithms suggests some obvious open problems:

Problem 1: find a polynomial-time algorithm that, given a binary matroid $M$, determines whether $M$ is an even cycle matroid.

Problem 2: find a polynomial-time algorithm that, given a ternary matroid $M$, determines whether $M$ is a signed-graphic matroid.

By “given a matroid $M$” I mean that $M$ is given as a rank oracle, or a matrix or pretty much in any reasonable form. Even though I believe these problems may be solved, I’m certainly not claiming that such algorithms would be easy to find, or to implement. Let me  elaborate a bit.

Since both these classes of matroids have a finite list of excluded minors (as implied by the Matroid Minor Project), one may think of using the excluded minors to solve Problems 1 and 2. However, finding the excluded minors for these classes seems an even harder problem than finding a recognition algorithm. What about a more direct approach?

Say that you want to decide whether a given matroid $M$ is an even cycle matroid. Maybe you’d like to decompose $M$ into smaller, 3-connected pieces (as for graphic or regular matroids). Here is the first difficulty: even cycle matroids are not even closed under 1-sums. It seems reasonable to restrict our attention to 3-connected matroids, since most algorithms for recognising graphic matroids work because a 3-connected graphic matroid has only one graphical representation. This is very much not the case for even cycle and signed-graphic matroids. Thus the need for some new ideas.

One approach could be the following:

1. take a small minor $N$ of $M$;
2. since $N$ is small we can check if it is an even cycle matroid and find all of its signed graph representations;
3. we can try to “grow” each of these graphical representations of $N$ into representations of $M$.

Step 3. is not hard, as long as you keep track of the deletions and contractions to go from $M$ to $N$. The problem is that this algorithm is not polynomial in the size of $M$. The reason is that in general we cannot bound the number of signed graph representations of an even cycle matroid, so starting from the few representations of $N$ we may grow into a lot of representations of an intermediate matroid. This happens when some signed graph representation of $N$ has blocking pairs, i.e. sets of two vertices intersecting every unbalanced cycle. More precisely, suppose that $N’$ is a one-element coextension of $N$ and $N$ has a signed-graph representation $\Omega$ with a blocking pair. Then it is possible that $(G,S)$ grows into signed graphs $\Omega_1$ and $\Omega_2$ which are both representations of $M$ (by “grows into” I mean that contracting the edge in $E(N’)-E(N)$ in any of these two signed graphs produces $\Omega$). When this happens, the two new signed graphs still have blocking pairs, so this doubling of representations may happen over and over again. Similar problems arise when trying this approach on signed-graphic matroids.

References

[CCW85] V. Chandru, C.R. Coullard, and D.K. Wagner, On the complexity of recognizing a class of generalized networks, Oper. Lett. 4 (1985), 75-78.

[CGW93] C.R. Coullard, J.G. del Greco, and D.K. Wagner, Recognising a class of bicircular matroids, Discrete Appl. Math. 43 (1993), 197-215.

[G92] J.G. del Greco, Characterizing bias matroids, Discrete Math. 103 (1992), 153-159.

[M07] A. Musitelli, Recognition of generalized network matrices, Thèse EPFL n° 3938, École Polytechnique Fédérale de Lausanne (2007).

[S81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.

6 thoughts on “Biased graphs and their matroids III”

1. Rong Chen on said:

Maybe there is a way to avoid blocking pairs.

• I think you need to deal with blocking pairs separately: if you can recognise even cycle matroids that have a representation with a blocking pair, then recognising the whole class shouldn’t be too hard.

• Rong Chen on said:

I just wonder why it becomes easy after I recognize even cycle matroids as even cycle matroids just lift matroids of signed graphs and signed graphs is a relative simple case for biased graphs, although in the process of recognizing even cycle matroids one can understand some useful strategy that maybe be used in the future.

• I just meant that if you can recognise even cycle matroids that have a representation with a blocking pair, then recognising the whole class of even cycle matroids shouldn’t be too hard. Recognising lift matroids in general may be NP-hard.

2. The result that Rudi and I proved (but that neither of us has time to write up, really), takes exactly the approach Irene outlined. However, we group the inequivalent representations together, such that the representations in each group are related by relatively straightforward operations called “cylinder twists”. They involve pairs of blocking pairs. If we add another operation, a kind of “rotation”, then we can in fact keep them all together in one big equivalence class, if my memory serves me right.

The difficulties for general signed graphs lie in “tangled” signed graphs: those with no two vertex-disjoint unbalanced cycles.

It was to be expected that our class was a lot easier to handle than general signed graphs, because of a structure theorem by Bert Gerards. See Theorem 3.10 in this paper by Slilaty and Qin:

http://www.wright.edu/~daniel.slilaty/Research/2006%20SGDecompositions.pdf

• Thanks for the explanation Stefan.

This site uses Akismet to reduce spam. Learn how your comment data is processed.