|
|
|
|
|
|
by btilly
3452 days ago
|
|
|
In this case the polynomial time algorithm is to test the graph against a finite list of forbidden minors. This has a reasonable exponent, but a constant dependent upon how long that finite list is. That finite list can be extremely long indeed. And in some cases, there is no way of finding or verifying the full list. |
|
|