Feedback Vertex Kayles Finding a wining strategy in a two-player combinatorial game

Abstract

In this thesis Feedback Vertex Kayles is discused. Feedback Vertex Kayles is a two-player combinatorial game on graphs in which players remove nodes positioned on cycles. We also use the name Feedback Vertex Kayles to denote the problem of exploring whether there is a winning strategy for the first player and most often what this strategy is. This problem is an interesting and complex problem expected to be PSPACE-complete. Apart from discussing the complexity of the problem as a whole, in this thesis we will look into Feedback Vertex Kayles on specific graph classes. We discuss a number of graph classes for which we can determine in polynomial or faster time whether there is a winning strategy. To help the reader better understand the specific results and proofs and to give a deeper understanding of Feedback Vertex Kayles, this thesis first gives a broad range of important definitions and basic insights for Feedback Vertex Kayles.