Revision history [back]

Okay, so what I want to say here is that the code that searches for a graph minor is extremely slow in situations where it should be able to respond instantaneously. Here's a function written by DSM when responding to my last question here:

def has_minor(G, H):
try:
    m = G.minor(H)
    return True
except ValueError: 
    return False

I run the following code:

t=cputime()
h=graphs.CompleteGraph(7)
print h.size()
g=graphs.CompleteBipartiteGraph(4,4)
print g.size()
has_minor(g,h)
cputime(t)

This code checks if a K_{4,4} graph has as a minor a K_7 graph. The output is:

21
16
59.187697999999983

This tells us that a K_7 has 21 edges and a K_{4,4} has 16, so there's no way that a K_{4,4} has as a minor a K_7. Minors must have less than or the same number of edges as the original graph. So, it shouldn't take almost a minute to tell me that there is no such minor. It should take 0.001 seconds, approximately, because it should first check that simple thing before actually trying to find minors.

Or, am I completely off here?

Okay, so what I want to say here is that the code that searches for a graph minor is extremely slow in situations where it should be able to respond instantaneously. Here's a function written by DSM when responding to my last question here:

def has_minor(G, H):
 try:
     m = G.minor(H)
     return True
 except ValueError: 
     return False

I run the following code:

t=cputime()
h=graphs.CompleteGraph(7)
print h.size()
g=graphs.CompleteBipartiteGraph(4,4)
print g.size()
has_minor(g,h)
cputime(t)

This code checks if a K_{4,4} graph has as a minor a K_7 graph. The output is:

21
16
59.187697999999983

This tells us that a K_7 has 21 edges and a K_{4,4} has 16, so there's no way that a K_{4,4} has as a minor a K_7. Minors must have less than or the same number of edges as the original graph. So, it shouldn't take almost a minute to tell me that there is no such minor. It should take 0.001 seconds, approximately, because it should first check that simple thing before actually trying to find minors.

Or, am I completely off here?

Okay, so what I want to say here is that the code that searches for a graph minor is extremely slow in situations where it should be able to respond instantaneously. Here's a function written by DSM when responding to my last question here:

def has_minor(G, H):
    try:
        m = G.minor(H)
        return True
    except ValueError: 
        return False

I run the following code:

t=cputime()
h=graphs.CompleteGraph(7)
print h.size()
g=graphs.CompleteBipartiteGraph(4,4)
print g.size()
has_minor(g,h)
cputime(t)

This code checks if a K_{4,4} graph has as a minor a K_7 graph. The output is:

21
16
59.187697999999983

This tells us that a K_7 has 21 edges and a K_{4,4} has 16, so there's no way that a K_{4,4} has as a minor a K_7. Minors must have less than or the same number of edges as the original graph. So, it shouldn't take almost a minute to tell me that there is no such minor. It should take 0.001 seconds, approximately, because it should first check that simple thing before actually trying to find minors.

Or, am I completely off here?

Okay, so what I want to say here is that the code that searches for a graph minor is extremely slow in situations where it should be able to respond instantaneously. Here's a function written by DSM when responding to my last question here:

def has_minor(G, H):
    try:
        m = G.minor(H)
        return True
    except ValueError: 
        return False

I run the following code:

t=cputime()
h=graphs.CompleteGraph(7)
print h.size()
g=graphs.CompleteBipartiteGraph(4,4)
print g.size()
has_minor(g,h)
cputime(t)

This code checks if a K_{4,4} graph has as a minor a K_7 graph. The output is:

21
16
59.187697999999983

This tells us that a K_7 has 21 edges and a K_{4,4} has 16, so there's no way that a K_{4,4} has as a minor a K_7. Minors must have less than or the same number of edges as the original graph. So, it shouldn't take almost a minute to tell me that there is no such minor. It should take 0.001 seconds, approximately, because it should first check that simple thing before actually trying to find minors.

Or, am I completely off here?