Graph minors

A graph H is a minor of a graph G if H is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from G. For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

Problem: Fix a graph H. Find a polynomial time algorithm that decides if a given graph G has H as one of its minors. The algorithm must be polynomial in the number of vertices of G.

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

Graph minors

Simple and hard problems I

Given that an integer p is prime, can you convince me in a reasonable amount of time of that fact? Stated otherwise: Is there a “short” formal argument that proves the fact that a given prime is indeed prime? Here “short” means that the argument can be written in O(P(\mathrm{log} \,n)) pages, for some polynomial P independent of n.

Notice that there is always a short proof of the fact that a given composite number is composite, namely a non-trivial factorization.

Formally this last statement means that the problem of the deciding if a given integer is composite is in NP.

The excercise is to prove that the problem of deciding if a given integer is prime is in NP.

 

Remarks: The formal argument mentioned in the explanation is usually called certificate. Notice that the size of the certificate must be polynomial in the logarithm of n because n is representable by \mathrm{log}\, n bits and thus the size of the input is \mathrm{log}\, n and not n.

Simple and hard problems I