For some undirected graph , a vertex cover is a subset of nodes where every edge of touches at least one of those nodes. The vertex cover problem looks for membership in the following language
NP-Complete
Info
is NP-Complete
Given a graph , a nondeterministic Turing machine can enumerate through all subsets of nodes with size and check if one of them gives a vertex cover. Thus .
To prove membership in NP-hard, we reduce from 3SAT. We map each boolean formula to some graph . For each variable , add nodes and to and connect them with an edge. Next, for each clause , add nodes to , and connect all of these together. Next we add edges between , , and .
If has variables and clauses, then our construction of will have nodes. Let , and note that every clause gadget requires two nodes, while each variable gadget needs one in order to cover every edge.
For a true assignment of , add the nodes corresponding to true literals to our vertex cover. Next, for each clause, fix one true literal, and add nodes corresponding to the other two literals to our cover. The edges in each gadget are covered, while the edges between the gadgets will be covered, as any false literals will be covered by the two literals in each clause.
If has a vertex cover with nodes, each variable gadget will only have one node set. Take this as our assignment, and observe each clause will have two nodes set. The unset node must have an edge covered by a node from a variable gadget, thus this will correspond to a true assignment of .
This reduction gives a graph of size , so we have a polytime reduction and is NP-complete.