This paper by me, Jing Huang, and Xuding Zhu, 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?
Complexity of cycle transverse matching problems. International Workshop on Combinatorial Algorithms. Ross Churchley, Jing Huang, and Xuding Zhu (2011). 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ℓ with ℓ≥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 C3 is polynomial and for each Cℓ with ℓ≥4 is NP-complete. Our results imply that the stable transversal problem for each Cℓ with ℓ≥4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C3 , when restricted to line graphs, is polynomial.
C4-transverse matchings generalize tatami tilings. My colleague Alejandro Erickson provedMonomino-Domino Tatami Coverings. Alejandro Erickson (2013). the NP-completeness of domino tatami tiling, i.e. the problem of finding perfect C4-transverse matchings among subgraphs of the square grid.
I am grateful to NSERC for funding this research with a Alexander Graham Bell Canada Graduate Scholarship.
One of the most recognizable features of Japanese architecture is the matted flooring. The individual mats, called tatami, are made from rice straw and have a standard size and 1×2 rectangular shape. Tatami flooring has been widespread in Japan since the 17th and 18th centuries, but it took three hundred years before mathematicians got their hands on it.