7
$\begingroup$

A minimally strongly connected digraph (MSC) is strongly connected (SC), while removal of any arc destroys this. That is, between any two vertices a, b there exists a directed path from a to b, while removal of any arc (a,b) renders b unreachable from a.

What is known about graph isomorphism for MSCs?

For example, is decision of graph isomorphism between MSCs GI-complete ("graph-isomorphism complete" -- as hard as deciding isomorphism between general digraphs), or is it poly-time decidable? There seems to be no literature on this subject.

Another question is about determining UMS(n), the number of isomorphism types of MSCs for n vertices. In the paper Minimal strong digraphs it is mentioned that UMS(n), in other words, the number of unlabeled MSC digraphs with n vertices, is "unknown": does there exist at least a superpolynomial lower bound for UMS(n)? Again, there seems to be nothing in the literature on this subject (so any information is welcome).

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Isomorphism of MSC digraphs is isomorphism-complete. Consider two connected undirected graphs $G,H$ with no vertices of degree 1. It is routine to see that connectivity and minimum degree at least 2 won't help you to determine whether $G$ and $H$ are isomorphic.

Now convert $G,H$ to digraphs $G',H'$ by replacing each edge with a directed 4-cycle using two new vertices. Precisely, replace each edge $\lbrace v,w\rbrace$ by the 4-cycle $v\to x_{v,w}\to w\to y_{v,w}\to v$, where $x_{v,w},y_{v,w}$ are new vertices not used anywhere else. Now note that $G',H'$ are MSC digraphs which are isomorphic iff $G,H$ are isomorphic.

On the second question I'm not aware of a complete answer. Some small numbers are on OEIS.

$\endgroup$
2
  • $\begingroup$ Nice! Thank you. Now a superpolynomial lower bound is easy, taking for example the superpolynomial lower bound for trees (converting them into digraphs). Just one question: I wonder why you excluded the connected undirected graphs with vertices of degree 1. The extreme case is a tree where the result of the conversion is MSC. In another words, adding an edge connected to a new vertex of degree 1 (in a connected undirected graph) is the same as adding a directed 4-cycle with 3 new vertices to a vertex in an MSC digraph (which preserves minimally strongly connectivity). $\endgroup$ Aug 24, 2017 at 13:54
  • $\begingroup$ @HodaAbbasi I excluded vertices of degree 1 just to be sure that they can't be confused with the $x$-type and $y$-type vertices after converting to an MSC. For example, if you convert a path of two vertices you get a directed 4-cycle and now you can't tell which are the original vertices and which are the new vertices. I think that is the only case, but proving it is more messy than just excluding vertices of degree 1 in the first place. $\endgroup$ Aug 24, 2017 at 22:38
3
$\begingroup$

This answer addresses only your question "What is known about graph isomorphism for MSCs?".

It seems (to me) that

  • A one-sentence answer to your first question is "Nothing is explicitly known about this, and yet in the literature results are waiting for you, notably results of Mader, with which you can prove that MSC admit practical isomorphism testing."
  • Yet (without having looked into the matter closely), my conjecture is that isomorphism of $n$-vertex MSC can be checked in time polynomial in $n$, and even practically so, and the mathematical essence of why this is so is contained in

Wolfgang Mader : Minimal n-fach zusammenhängende Digraphen. Journal of Combinatorial Theory B, Volume 38, Issue 2, April 1985, Pages 102-117

Why? Very briefly, the reason for my conjecture is that

  • Mader gives a proof of structural properties of MSC (in the direction of 'tree-likeness of certain substructures' and also of sparsity), properties which you can probably put to use, if you combine these structure theorems with the very well studied topics of

  • isomorphism testing for bounded-degree undirected graphs

  • isomorphism testing for tree-like graphs

to write out a full proof of the above conjecture.

Sadly, it will not be possible for me to really work on this. However,

  • If you need help with the German in Mader's article only, that is easy, and I think I can help you with this, though if you have access to large search engines, the language should not be much of a barrier. Mader's paper is clearly written. (Detail which seems useful to point out: Mader writes '$E(D)$' for the vertex set of the digraph, presumably because the German for 'vertex' is 'Ecke', and '$K(D)$' for the arc set.)

  • As far as I know, regrettably, an English exposition of Mader's proofs does not yet exist.

  • Mader's results are mentioned in the nice monograph of Bang-Jensen and Gutin, but, sadly, a proof is not given.

  • I once started working out an exposition of these results of Mader's, yet, sadly, never finished.

  • Depending on what you like/have to do, working out a complete exposition and/or new proof of Mader's above article might be a useful project, for you and others.

Getting briefly back to the subject matter of Mader's article, my recommendation (no guarantee that it will really work out, needless to say) is that

  • you start by focusing on 'Korollar 2' in loc. cit., specialized to $n=1$, which gives you a (to my mind) highly-non-trivial structure-theorem on MSC, and then try to exploit this statement to construct an efficient1 isomorphism-testing algorithm for MSC.

Good luck.

1 ....and maybe even practical...note that Mader's proof is written for every digraph, no 'hidden constants' or 'huge $n$' or the like.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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