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!

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 13 '11 at 20:52
  • $\begingroup$ 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 $\endgroup$ – Harry Stern May 14 '11 at 2:26
  • $\begingroup$ 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. $\endgroup$ – Graphth May 17 '11 at 18:15

Sorry for the answer on an extremely old question but I came across it and could not ignore it. These are the things I came up with in worst case nlogn time you can sort all the degrees adn compare them. if there is a single time in which position x in the sorted list of B is smaller than the same position x in the sorted list of A . B cannot be a minor of A. same thing goes with the length of edges (non existant lengths and degrees are set to minus infinity).


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.