Let G=(V,E) be an undirected graph (V is the set of vertices and E is the set of edges of G). A set of vertices X of G (a subset of V) is a vertex cover if every edge of G has at least one end in X. The problem is, given an undirected graph G and an integer k, to decide whether G has a vertex cover with no more than k vertices and, if so, to compute it.

INPUT: An undirected graph and an integer k. The graph is given by the set of ground atoms "vtx(v)" for v=1,2,..., n (where n is the number of vertices), and "edge(x,y)". Note: x needs not to be less than y. However, for every (undirected) edge {x,y} only one atom "edge(x,y)" or "edge(y,x)" is present.

OUTPUT: a set of vertices that is a vertex cover of G of size no more than k

DATA SETS:

In each case, the vertex set is {1,2,...,100}, the edge set has 200
elements; only the edges are listed in the data sets given below.

vc1
(minimum size vertex cover - 53)

vc2
(minimum size vertex cover - 50)

vc3
(minimum size vertex cover - 55)

vc4
(minimum size vertex cover - 54)

NOTES: