Complexity of cycle-transverse matching problems

Paper with Jing Huang and Xuding Zhu presented at IWOCA 2011

Two weeks after CanaDAM, UVic hosted the International Workshop on Combinatorial Algorithms. I presented a paper by me, Jing Huang, and Xuding Zhu which gives the first results of what would become my master’s thesis. It studies the computational complexity of the following problem: in a given graph, is there a matching which breaks all cycles of a given length?

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of HH 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 CC_\ell with 3\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 HH. We show that the problem for C3C_3 is polynomial and for each CC_\ell with 4\ell \geq 4 is NP-complete. Our results imply that the stable transversal problem for each CC_\ell with 4\ell \geq 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C3C_3 , when restricted to line graphs, is polynomial.

Ross Churchley, Jing Huang, and Xuding Zhu [1]

Slides of the talk can be found here (PDF). I am grateful to NSERC for funding this research with a Alexander Graham Bell Canada Graduate Scholarship.


  1. Complexity of cycle transverse matching problems. International Workshop on Combinatorial Algorithms. Ross Churchley, Jing Huang, and Xuding Zhu (2011). ↩︎