- INSTANCE: Graph .
- 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).*Bad News:*APX-complete [471].*Comment:*Transformation from MINIMUM VERTEX COVER.*Garey and Johnson:*GT10