I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?

  • 4
    $\begingroup$ I wish ! that would be an excellent ALENEX/SEA paper or set of papers. $\endgroup$ Commented Feb 23, 2014 at 18:26

1 Answer 1


NAUTY can be used as a library to help you build a hashtable for the entire poset of graph minors for small $n$. The key would be the cannonial form given by NAUTY and the value would be a concatenation in sorted order of the cannonical forms of it's direct minors.

  • $\begingroup$ Yes, but nauty doesn't (as far as I know) provide any methods for finding minors in the first place. Also, given that the question was about merely the presence/absence of a specific set of minors, I don't see how building a hashtable out of all instances helps solve that initial problem... $\endgroup$ Commented Feb 26, 2014 at 22:25
  • $\begingroup$ Wendy Myrvold and Brendan McKay do a lot of graph minor research with NAUTY as a support library. DFS on deletions/joins until you get down to a tractable number of vertices then query the pre-computed poset. How you do the DFS will depend on what type of minor you are looking for. $\endgroup$ Commented Feb 26, 2014 at 22:41
  • $\begingroup$ Interesting! You should make that part of the answer. Also, can you give a reference? I couldn't find it. $\endgroup$ Commented Feb 26, 2014 at 22:46

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.