Graph Transversals for Hereditary Graph Classes: a Complexity Perspective

Abstract

Within the broad field of Discrete Mathematics and Theoretical Computer Science, the theory of graphs has been of fundamental importance in solving a large number of optimization problems and in modelling real-world situations. In this thesis, we study a topic that covers many aspects of Graph Theory: transversal sets. A transversal set in a graph G is a vertex set that intersects every subgraph of G that belongs to a certain class of graphs. The focus is on vertex cover, feedback vertex set and odd cycle transversal.

The decision problems Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal ask, for a given graph G and an integer k, whether there is a corresponding transversal of G of size at most k. These problems are NP-complete in general and our focus is to determine the complexity of the problems when various restrictions are placed on the input, both for the purpose of finding tractable cases and to increase our understanding of the point at which a problem becomes NP-complete. We consider graph classes that are closed under vertex deletion and in particular H-free graphs, i.e. graphs that do not contain a graph H as an induced subgraph.

The first chapter is an introduction to the thesis. There we illustrate the motivation of our work and introduce most of the terminology we have used for our research. In the second chapter, we develop a number of structural results for some classes of H-free graphs.

The third chapter looks at the Subset Transversal problems: there we prove that Feedback Vertex Set and Odd Cycle Transversal and their subset variants can be solved in polynomial time for both P_4-free and (sP_1+P_3)-free graphs, while for Subset Vertex Cover we show that it can be solved in polynomial time for (sP_1+P_4)-free graphs.

The fourth chapter is entirely dedicated to the Connected Vertex Cover problem. The connectivity constraint requires additional proof techniques. We prove this problem can be solved in polynomial time for (sP_1+P_5)-free graphs, even when weights are given to the vertices of the graph.

We continue the research on connected transversals in the fifth chapter: we show that Connected Feedback Vertex Set, Connected Odd Cycle Transversal and their extension variants can be solved in polynomial time for both P_4-free and (sP_1+P_3)-free graphs.

In the sixth chapter we study the price of independence: can the size of a smallest independent transversal be bounded in terms of the minimum size of a transversal? We establish complete and almost-complete dichotomies which determine for which graph classes such a bound exists and for which cases such a bound is the identity.