18

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?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
Hooman
  • 289
  • 1
  • 2

1 Answers1

5

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.

Chad Brewbaker
  • 2,359
  • 15
  • 18
  • 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