A good Library for testing whether a minors exists in a graph?

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?

• I wish ! that would be an excellent ALENEX/SEA paper or set of papers. – Suresh Venkat Feb 23 '14 at 18:26

1 Answer

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.

• 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... – Joshua Grochow Feb 26 '14 at 22:25
• 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. – Chad Brewbaker Feb 26 '14 at 22:41
• Interesting! You should make that part of the answer. Also, can you give a reference? I couldn't find it. – Joshua Grochow Feb 26 '14 at 22:46