Re: Not constructive proof of existing of an algorithm



Check out David Johnson's NP-completeness column
number #19. It gives a few remarkable examples that
arise in the Robertson-Seymour graph minors work.

http://www.research.att.com/~dsj/columns/col19.pdf

.