On graph-transverse matchings

On graph-transverse matchings

Master's thesis at the University of Victoria

I have successfully defended my master’s thesis on graph-transverse matching problems! The thesis considers the problem of deciding whether a given graph G admits a matching which covers every copy of a fixed tree or cycle. It contains a number of results, including a refinement of my paper on cycle-transverse matchings and new algorithms and NP-completeness results for tree-transverse matching problems.

Given graphs GG, HH, is it possible to find a matching which, when deleted from GG, destroys all copies of HH? The answer is obvious for some inputs—notably, when GG 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 HH is a fixed tree or cycle; our aim is to identify those HH for which it can be solved efficiently.

The HH-transverse matching problem, TM(H)\text{TM}(H) for short, asks whether an input graph admits a matching MM such that no subgraph of GMG-M is isomorphic to HH. The main goal of this thesis is the following dichotomy. When HH is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an HH-transverse matching if one exists. However, TM(H)\text{TM}(H) is NP-complete when HH is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.

Ross Churchley [1]

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.

  1. On graph-transverse matching problems. Ross Churchley (2012). ↩︎