7
$\begingroup$

For an undirected graph, my "intuitive" understanding of a minor is that I take a subgraph, partition it's vertex set into connected subsets and contract each subset into a single vertex.

If I try the same definition with a directed graph (=digraph), I have the problem that there is a distinction between weakly connected and strongly connected. Even so I saw a definition where connected was simply replaced by weakly connected during my research for this question, such a definition doesn't seem to be very useful, or at least doesn't coincide with my "intuition" about what a minor for a digraph should be. What I don't like about that definition is that there might exist more directed paths after the contraction of the subsets into single vertices than there were before.

Has anybody seen a definition of minors for digraphs that better matches my "intuition"? Any references to a book or paper (even if not available online)? Of course, I don't mind if the concept isn't called "minor", I just care for the concept itself.

  • 1
    The definition of a source/sink node is more general than a single vertex. If you wait till I release the first two parts of my series, they have proofs that "any infinite sequence of arbitrary orientations of bounded-treewidth graphs with any additional undirected edges are well-quasi-ordered". I will release them in couple of months along with the path-width paper mentioned in http://arxiv.org/abs/1308.51702013-12-07

2 Answers 2

6

In general there is no "official" generalization of edge contraction to digraphs:

This is a quote from the objectives of "New Trends on Structural Graph Theory" 09/2010:

Graph minors on undirected graphs are reasonably understood right now, but graph minors on directed graphs are not. For instance, which edges are allowed to contract? There are other fundamental questions in directed graphs.

In more specific cases it seems that individual researchers tend to pick and choose a definition of digraph minor that seems the most natural for their particular problem. See here, here, and here (if you have access) for three published works each using their own version of the edge contraction operator.

One thing to consider is that you can use vertex and edge deletions to create graph minors, and by carefully pruning first you can then contract vertices without creating additional edges or loops.

  • 0
    You are absolutely right. I don't know what definition would provide the "right" amount of balance between needing to contract edges and needing to be able to still have functionality from the graph-minor's attributes.2011-08-19
2

Since I seem to have some "intuition" about what "should" be a digraph-minor and what "shouldn't", I decided to test my "intuition" on some digraphs. A minor is actually the composition of taking a subgraph and "taking an M-graph". Because there is no confusion what is meant by "taking a subgraph", only "taking an M-graph" needs clarification.

In the picture below, the digraph on the right is an M-graph of the digraph on the left (and of the digraph in the middle), but the digraph in the middle is not an M-graph of the digraph on the left (according to my "intuition", because $a2$ should not be reachable from $a3$).

original graph , no digraph minor , digraph minor

Edit 1 It may be a good idea to restrict contractions to weakly connected subsets, so I slightly modified the definition of an M-graph (which is intended to formalize my "intuition"):

A digraph $G'=(V',E')$ is an M-graph of a digraph $G=(V,E)$, if there is a surjective function $\varphi:V \mapsto V'$ such that

  1. $\varphi^{-1}(\{v'\})$ is a weakly connected subset of $G$ for all $v'\in V'$,
  2. every walk on $G'$ is the image under $\varphi$ of a walk on $G$, and
  3. every image under $\varphi$ of a walk on $G$ is a walk on $G'$.

Here a walk on a digraph $G=(V,E)$ is a sequence $v_0, v_1, \ldots, v_n$ of vertices from $V$ such that $(v_i,v_{i+1})\in E$. The image of a walk under a function $\varphi$ is the sequence of the images of the vertices of the walk, where identical successive vertices have been replaced by a single vertex.

This gives the following definition of a minor for a digraph:

A digraph $X$ is a minor of a digraph $Y$, if $Y$ contains a subgraph $Z$ for which $X$ is an M-graph.

There are cases where this definition allows more minors than my "intuition":

ambiguous

There are also cases where all subsets must be contracted at the same time, showing that incremental constructions contracting one edge or subset at a time won't work (in general) for this definition of digraph minor:

diminor

It should be possible to prove some useful properties for this definition of digraph minor. However, this doesn't necessarily answer the question whether this definition of a minor of a digraph is actually useful.

Edit 2 The above minor relation is not a well quasi ordering, as shown by the following counterexample:

no wqo

Maybe it's not such a good idea after all to restrict contractions to weakly connected subsets. But even without this restriction, it's unclear whether the corresponding minor relation would be a well quasi ordering.