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.
The thesis is related to my previous work on
and, roughly speaking, shows that -transverse matchings are NP-hard to find when is a big cycle or tree, and tractable when is a triangle or a small tree.
On graph-transverse matching problems. Ross Churchley (2012). Given graphs , , is it possible to find a matching which, when deleted from , destroys all copies of ? The answer is obvious for some inputs—notably, when 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 is a fixed tree or cycle; our aim is to identify those for which it can be solved efficiently.
The -transverse matching problem, for short, asks whether an input graph admits a matching such that no subgraph of is isomorphic to . The main goal of this thesis is the following dichotomy. When is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an -transverse matching if one exists. However, is NP-complete when 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.
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?
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.