TADM2E 5.15

From Algorithm Wiki
Revision as of 01:36, 1 January 2017 by Joky (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

To build a vertex cover, we need to keep at least one vertex for each edge. The independent set requires at most one vertex for each edge.

Together it means we need to keep only exactly one vertex for each edge, this reduces to two-colour graph problem.