Research

My current research interests involve graph theory, game theory and matroid theory. 

For graphs, I am mostly interested in finding structure theorems or algorithmic results for certain classes of tournament graphs (namely complete graphs with orientations). For most problems on tournaments, it is not hard to show that they are NP-complete, but the situation could be quite different for some subclasses of tournaments. For example, I have studied the maximum independent set problem on U5-free tournaments and showed that for this class of tournaments, the maximum independent set problem is in P while it is NP-complete for all tournaments.

For games, I study games on graphs. One example: Alice and Bob are coloring a graph G with n colors. The rule is that Alice colors one vertex then Bob colors another vertex until all vertices are colored properly. If at some step, there is a vertex that could not be properly colored, Bob wins. Otherwise, Alice wins. One interesting yet open question is: suppose Alice has a winning strategy on G with k colors, does Alice also have a winning strategy on G with (k+1) colors?

For matroids, I am currently working on pinch-graphic matroids. Pinch-graphic matroids are matroids that can be represented as the even-cycle matroid of a signed graph with two vertices intersecting all odd cycles. Pinch-graphic matroids are close to graphic matroids and they are minor-closed. I am working on finding the excluded minors for pinch-graphic matroids with my supervisor, Bertrand Guenin. Our first attempt limits to bound the number of excluded matroids for pinch-graphic matroids that are 3-connected.

1.  Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments

Submitted.  With Sophie Spirkl.