Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The diploma thesis Über Minoren gerichteter Graphen by Steffen Seidler might be illuminating, especially if German is your first language. –  Thomas Klimpel Dec 6 '13 at 0:26
    
Shiva Kintali introduces a paper about Forbidden Directed Minors and Kelly-width and announces "As mentioned in the paper, I have a series of upcoming papers (called Directed Minors) making progress towards a directed graph minor theorem (i.e., all digraphs are well-quasi-ordered by the directed minor relation)." It might be interesting to see whether the counterexample given under Edit 2 below also applies to his notion of directed minor relation. –  Thomas Klimpel Dec 6 '13 at 1:24
    
In my paper available at arxiv.org/abs/1308.5170 , there is an operation called "Source Contraction". Using this operation we can show that the infinite list mentioned in Edit 2 is not a counterexample. –  Shiva Kintali Dec 6 '13 at 2:35
    
@ShivaKintali Are you sure? No digraph in the infinite list contains a source or a sink. It seems to me that the digraph obtained via "Source Contraction" will contain at least one source, and I don't see how you will be able to get back to a source and sink free digraph. In addition, all contraction operations from the paper seem to be compatible with the notion of digraph minor used in the answer. Hence I would be surprised if the counterexample didn't apply. –  Thomas Klimpel Dec 6 '13 at 23:03
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 arxiv.org/abs/1308.5170 –  Shiva Kintali Dec 7 '13 at 5:35
add comment

2 Answers

up vote 6 down vote accepted

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.

share|improve this answer
    
For my "intuition" about digraph-minors, contraction of strongly connected subsets of vertices should definitively be allowed. But I have the impression that any definition trying to work with individual vertex and edge deletions will have difficulties to allow this without allowing too much (like contraction of weakly connected subsets of vertices). –  Thomas Klimpel Aug 18 '11 at 23:53
    
@Thomas I agree with you completely. But if you limit your partitions to only strongly connected subsets, for many digraphs it may only be possible to define a very limited number subsets having more than one vertex, after you have collected the strong component into one subset. –  user12998 Aug 19 '11 at 0:23
    
I don't want to limit partitions to only strongly connected subsets. I just doubt that "edge contraction operators" will be able to do the trick. If working with "contraction operators", at least some version of "subset contraction operator" seems to be required. –  Thomas Klimpel Aug 19 '11 at 6:56
    
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. –  user12998 Aug 19 '11 at 19:11
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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