Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 2011-05-13 14:37:31 -0500

DSM gravatar image

When you're working with Sage, it really is worth reading the code directly. It's often the case that no one optimized for a use case they didn't need. From the documentation (Graph.minor?):

   COMPLEXITY:

   Theoretically, when H is fixed, testing for the existence of a
   H-minor is polynomial. The known algorithms are highly exponential
   in H, though.

   Note: This function can be expected to be *very* slow, especially where
     the minor does not exist.

And when you look at the code (Graph.minor??) you see that it doesn't do any checking beforehand, it simply dives right in and treats it as a linear program.

In the short term, you can simply add whatever give-up-early checks you want to has_minor yourself. In the medium term, we should probably patch this; are you interested in writing one? It would be pretty simple, and I can help shepherd you through the process. Wasn't so very long ago I submitted my first patch! Warning: it can be addictive. :^)