Effective data reduction for strongly stable matching in very sparse graphs

We provide a linear-time computable problem kernel of linear size for Strongly Stable Roommates parameterized by the feedback edge number of the acceptability graph (which encodes which agents may be matched to each other). • A linear problem kernel for Strongly Stable Matching is provided. • Stability of a matching is sensible to vertex/edge deletion. • Introduction of annotated problem version helps to design reduction rules.