8
$\begingroup$

I know very little graph theory. I am trying to determine if one graph, A, has as a minor another graph, B. I know the problem is slow in general, so I am looking for things that I might be able to see quickly.

For example, I know a minor is going to have less edges than the original graph (maybe technically it could have the same number). So, if B has more edges than A, I know B is not a minor of A right away.

Are there any other things like this? Perhaps looking at the degree sequences? Maybe A has more edges than B but the degree sequences are such that we can quickly tell B is definitely not a minor of A?

EDIT: I guess the question could be stated: Are there any minor monotone graph parameters that can be computed quickly? Order and size would be two but they aren't all that powerful.

Any help would be much appreciated! Thanks!

  • 0
    If $B$ is fixed then there is an $O(n^3)$ algorithm, though the constant is horrible, and I'm not sure that the proof is even entirely constructive.2011-05-13
  • 0
    To expand on Yuval's comment, by the graph minor theorem there exists an algorithm but the proof is nonconstructive. For certain classes of graphs you can do better. [wikipedia](http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem#Polynomial_time_recognition)2011-05-14
  • 0
    Dear all, thanks for the info, but these are not answers to my question. I'm just looking for little tweaks that could speed up an already existing implementation.2011-05-17

1 Answers 1