Content deleted Content added
rm unneeded elaboration and citation |
|||
Line 27:
=== Sub-graphs ===
The problem of [[decision problem|deciding]] whether a graph <math>G</math> contains <math>H</math> as a [[graph minor|minor]] is [[NP-complete]] in general, but where <math>H</math> is fixed, it can be solved in polynomial time. The running time for testing whether <math>H</math> is a minor of <math>G</math> in this case is <math>O(n^2)</math>,<ref name="kkr12">{{cite journal |author1=Kawarabayashi, K. I. |author2=Kobayashi, Y. |author3=Reed, B. |year=2012 |title=The disjoint paths problem in quadratic time |journal=Journal of Combinatorial Theory, Series B |volume=102 |issue=2 |pages=424–435|doi=10.1016/j.jctb.2011.07.004 |doi-access=free }}</ref> where <math>n</math> is the number of vertices in <math>G</math> and the [[big O notation]] hides a constant that depends superexponentially on <math>H</math>. The constant is greater than <math>2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ) </math> in [[Knuth's up-arrow notation]], where <math>h</math> is the number of vertices in <math>H</math>.<ref>{{cite journal |author=Johnson, David S. |title=The NP-completeness column: An ongoing guide (edition 19) |journal= Journal of Algorithms |volume=8 |issue=2 |year=1987 |pages=285–303 |citeseerx=10.1.1.114.3864 |doi=10.1016/0196-6774(87)90043-5 }}</ref> Even the case of <math>h = 4</math> cannot be reasonably computed as the constant is greater than <math>{\ \atop {\ }} {{\underbrace{2^{2^{\cdot^{\cdot^{2}}}}}} \atop n}</math> with ''n'' = 65536
=== Cryptographic breaks ===
| |||