UC Santa Barbara

An independent set in a graph $G$ is a collection of vertices with no edge between any two. The {\sc Independent Set} problem is a classic {\sc NP}-Hard problem that takes in a graph $G$ and the task is to find an independent set in $G$ of maximum size. An induced subgraph of $G$ is another graph, $H$, where the vertex set of $H$ is a subset $V(H) \subseteq V(G)$, and the edge set of $H$ is all edges $uv$ in $E(G)$ where $u,v \in V(H)$. A graph is said to be $H$-free if it does not contain $H$ as an induced subgraph. Lastly, quasi-polynomial functions are functions that grow (slightly) faster than polynomial functions by allowing poly-log terms in their exponents, for example, $n^{log^2(n)}$ is a quasi-polynomial function.

In this thesis, we will provide a quasi-polynomial time algorithm for {\sc Independent Set} on $P_k$-free graphs \cite{gartlandpkfree}, where $P_k$ denotes a path with $k$ vertices. We will later extend this result in multiple ways. First, we give a quasi-polynomial time algorithm for {\sc Independent Set} as well as related problems, such as {\sc Feedback Vertex Set} on $C_{>k}$-free graphs \cite{GartlandLPPR21}, which are graphs that do not contain induced cycles with more than $k$ vertices. Additionally, we will give a quasi-polynomial time algorithm for {\sc Independent Set} on $H$-free graphs where $H$ is a forest of paths and subdivided claws \cite{gartland2023maximum}. A subdivided claw is a graph formed by taking three paths of any desired length along with a vertex $v$ that is a neighbor of exactly one end vertex in each of the three paths. This last result resolves an open problem first investigated by Alekseev~\cite{Alekseev82} in 1982.

In a seemingly different research thread, we will characterize graph classes with few minimal separators \cite{gartland2020dominated, doi:10.1137/1.9781611977554.ch120}. A minimal separator is a set $S$ such that there are two vertices $u,v$ in different components of $G-S$ and for any proper subset $S' \subset S$, $u$ and $v$ are in the same component of $G-S'$. A class ${\cal F}$ of graphs is called tame if every graph in ${\cal F}$ on $n$ vertices contains at most $n^{O(1)}$ minimal separators, {\em quasi-tame} if every graph in ${\cal F}$ on $n$ vertices contains at most $n^{\log^{O(1)}(n)}$ minimal separators, and {\em feral} if there exists a constant $c>1$ so that $\cal F$ contains $n$-vertex graphs with at least $c^n$ minimal separators for arbitrarily large $n$. The classification of graph classes into (quasi) tame or feral has numerous algorithmic consequences and has recently received considerable attention. In particular, {\sc Independent Set} and related problems can be solved in polynomial time on tame graph classes and quasi-polynomial time on quasi-tame graph classes \cite{FominTV15}.

An essential tool that both our characterization of quasi-tame graph classes and our quasi-polynomial time algorithms depend on are {\em dominated balanced separators}, which are vertex sets $S$ of a graph $G$ that are dominated by a constant number of vertices, and no component of $G-S$ has over, say, half of $G$'s vertices. In the introductory chapter of this thesis, we give a conjecture on dominated balanced separators that we refer to as the Induced Grid Minor Conjecture. If true, it would unify many of the results in this thesis and give efficient algorithms for {\sc Independent Set} and related problems on many graph classes for which such algorithms have long been sought with no success, such as even-hole-free graphs. Additionally, if this conjecture is true, we believe it could serve as a building block for additional interesting theorems for hereditary graph classes.