18
$\begingroup$

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?

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

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.

$\endgroup$
  • $\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$ – Joshua Grochow Feb 26 '14 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$ – Chad Brewbaker Feb 26 '14 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$ – Joshua Grochow Feb 26 '14 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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