TADM2E 9.7

From Algorithm Wiki
Jump to: navigation, search

Construct an instance of the given problem from vertex cover as follows: Create a set of edges for each vertex, u, where the set contains all the edges that have one vertex in u.

Let the large set, X, be the set of all the edges in the graph.

Proofs up to you.