Next: MAXIMUM TRIANGLE PACKING Up: Covering and Partitioning Previous: MINIMUM FEEDBACK ARC SET Index

### MINIMUM MAXIMAL MATCHING

- 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., |E'|.

- Good News: Approximable within 2 (any maximal matching).

- Bad News: APX-complete [448].

- Comment: Transformation from MINIMUM VERTEX COVER.

- Garey and Johnson: GT10