Galactic algorithm: Difference between revisions

Revision as of 02:00, 24 May 2019

Revision as of 10:10, 24 May 2019

Line 17:

| title = Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)

| year = 2012}}.</ref>

*The problem of [[decision problem|deciding]] whether a graph ''G'' contains ''H'' as a [[graph minor|minor]] is NP-complete in general, but where ''H'' is fixed, it can be solved in polynomial time. The running time for testing whether ''H'' is a minor of ''G'' in this case is ''O''(''n''²),<ref name="kkr12">{{harvtxt|Kawarabayashi|Kobayashi|Reed|2012}}.</ref> where ''n'' is the number of vertices in ''G'' and the [[big O notation]] hides a constant that depends superexponentially on ''H''. The constant is greater than (using [[Knuth's up-arrow notation]]), and where where ''h'' is the number of vertices in ''H'':<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 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.3864&rep=rep1&type=pdf}}</ref>

::<math> c > 2 \uparrow \uparrow (2 \uparrow \uparrow (2 \uparrow \uparrow (h/2) ) ). </math>