# Complexity of cycle-transverse matching problems

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of $$H$$ in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each $$C_\ell$$ with $$\ell \geq 3$$ is NP-complete. In this paper, we study an edge version of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of $$H$$. We show that the problem for $$C_3$$ is polynomial and for each $$C_\ell$$ with $$\ell \geq 4$$ is NP-complete. Our results imply that the stable transversal problem for each $$C_\ell$$ with $$\ell \geq 4$$ remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for $$C_3$$ , when restricted to line graphs, is polynomial.

Complexity of cycle-transverse matching problems. Ross Churchley, Jing Huang, and Xuding Zhu. Lecture Notes in Computer Science 7056, 135–143. 2011.