MINIMUM MAXIMAL MATCHING (original) (raw)

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

INSTANCE:Graph $G=\left(V,E\right)$ .
SOLUTION:A maximal matching E', i.e., a subset $E'\subseteq E$ 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., $\vert E'\vert$ .
_Good News:_Approximable within 2 (any maximal matching).
_Bad News:_APX-complete [471].
_Comment:_Transformation from MINIMUM VERTEX COVER.
Garey and Johnson: GT10

Viggo Kann
2000-03-20