I have successfully defended my master’s thesis on graph-transverse matching problems! It considers the computational complexity of deciding whether a given graph admits a matching which covers every copy of a fixed tree or cycle.
and, roughly speaking, shows that H-transverse matchings are NP-hard to find when H is a big cycle or tree, and tractable when H is a triangle or a small tree.
On graph-transverse matching problems. Ross Churchley (2012). Given graphs G, H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is "no" — but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently.
The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G−M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.
Slides of my defence can be found here. I am grateful to NSERC for funding my degree with a Alexander Graham Bell Canada Graduate Scholarship, and to my supervisor Jing Huang.
Complexity of cycle-transverse matching problems
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?
Line-polar graphs: characterization and recognition
This paper is the result of the research term I took as an undergraduate in the summer of 2009. It studies the edge versions of the monopolar and polar partition problems, and presents a linear-time solution to both.