\input zb-basic
\input zb-ioport
\iteman{io-port 05997049}
\itemau{Churchley, Ross; Huang, Jing; Zhu, Xuding}
\itemti{Complexity of cycle transverse matching problems.}
\itemso{Iliopoulos, Costas S. (ed.) et al., Combinatorial algorithms. 22nd international workshop, IWOCA 2011, Victoria, BC, Canada, July 20--22, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-25010-1/pbk). Lecture Notes in Computer Science 7056, 135-143 (2011).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{stable transversal problem; transverse matching problem; algorithm; complexity}
\itemli{doi:10.1007/978-3-642-25011-8\_11}
\end