Transversal Problems In Sparse Graphs

Abstract

Graph transversals are a classical branch of graph algorithms. In such a problem, one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs~$F$ from a fixed family $\mathcal F$.

In the first portion of this thesis we show two results related to even cycle transversal. %%Note rephrase this later. In Chapter \ref{ECTChapter}, we present our 47/7-approximation for even cycle transversal. To do this, we first apply a graph ``compression" method of Fiorini et al. % \cite{FioriniJP2010} which we describe in Chapter \ref{PreliminariesChapter}. For the analysis we repurpose the theory behind the 18/7-approximation for ``uncrossable" feedback vertex set problems of Berman and Yaroslavtsev %% \cite{BermanY2012} noting that we do not need the larger ``witness" cycles to be a cycle that we need to hit. This we do in Chapter \ref{BermanYaroChapter}.

In Chapter \ref{ErdosPosaChapter} we present a simple proof of an Erdos Posa result, that for any natural number $k$ a planar graph $G$ either contains $k$ vertex disjoint even cycles, or a set $X$ of at most $9k$ such that $G \backslash X$ contains no even cycle.

In the rest of this thesis, we show a result for dominating set. A dominating set $S$ in a graph is a set of vertices such that each node is in $S$ or adjacent to $S$. In Chapter 6 we present a primal-dual $(a+1)$-approximation for minimum weight dominating set in graphs of arboricity $a$. At the end, we propose five open problems for future research.