# On graph-transverse matchings

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 $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, $\text{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, $\text{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.