Directed graph minor theorems

Question

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)

Answer 1

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.