In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition

A directed graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges.

Since then, many more notions of a “directed graph minor” have arisen in various context (see here and here for examples and references). One of the goals in defining these notions is that the definition Robertson and Seymour gave doesn’t obviously capture the notion that if $G$ is a minor of $H$, then $G$ should be “simpler” than $H$.

I’m looking for references to proofs of the graph minor theorem for these more restrictive definitions of “graph minor.” I’m particularly interested in the following definition (Johnson et al., 2001):

A graph $G’$ is a butterfly minor of a directed graph $G$ if $G’$ can be obtained from $G$ by a sequence of the following local operations:

  1. Deleting an edge (a, b);
  2. Contracting an edge (a, b) where b has indegree 1;
  3. Contracting an edge (a, b) where a has outdegree 1.

But other definitions would also interest me, especially if they’re amenable to analyzing computational graphs of circuits or ML devices (neural networks, Bayesian networks)


So directed graphs are not well-quasi-ordered by butterfly minors; see the intro of [BPP]. Furthermore, there are reasons to think that many of the FPT results for graph minors may not hold in the directed setting (ie [PW]).

Yet, perhaps surprisingly, it may still be possible to get a structure theorem for butterfly minors! There is an ongoing project to do this; I believe the most recent paper is "The Directed Flat Wall Theorem" by Giannopoulou, Kawarabayashi, Kreutzer, and Kwon. If you Google the authors you should be able to find more information about the project. This is a big task and the results so far are exciting.

Also notable, there is a relationship between "matching-minors" of (undirected) bipartite graphs and butterfly minors; see [HRW]. Furthermore, Johnson's thesis "Eulerian digraph immersion" is on a different kind of directed minor for 4-regular, directed, Eulerian graphs (same Johnson as mentioned in the question).

I'm not really sure why any of these definitions would be useful for studying graphs of circuits or graphs in machine learning, but I sure hope they are! It's nice to see interest from this direction, and I hope something in the post is helpful.

| cite | improve this answer | |
  • 2
    $\begingroup$ Thank you for the references! For anyone curious, the counterexample to the graph minor theorem for butterfly minors is $C_{2k}$, where the arcs alternate directions. My motivation for using these in machine learning is that I'm looking at the structure of neural networks. It turns out that if $G\triangleleft H$ and $H$ cannot be trained to compute $f$ then neither can $G$. $\endgroup$ – Stella Biderman Aug 1 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.