SOLUTION:
A maximal matching E', i.e., a subset
such that
no two edges in E' shares a common endpoint and every edge in
E-E' shares a common endpoint with some edge in E'.
MEASURE:
Cardinality of the matching, i.e., .
Good News:
Approximable within 2 (any maximal matching).
.
such that
no two edges in E' shares a common endpoint and every edge in
E-E' shares a common endpoint with some edge in E'.
.