TADM2E 9.7

From Algorithm Wiki
Revision as of 18:24, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.