Research Projects

The project summary consists of two parts: PART 1: Structure and Coloring of Graphs and Digraphs Problem 1: A longstanding conjecture of Seymour states that in every oriented graph there is a vertex whose second out-neighbourhood is at least the size of its out-neighbourhood. One aim of the project is to explore fundamental invariants in oriented graphs such as the conjecture in more detail and make some progress on interesting graph classes and closely related problems. Problem 2: We would look to explore the Erdős-Neumann-Lara conjecture which states that for every integer k, there exists an integer f(k), such that if χ(G) ⩾ f (k),, then the dichromatic number of G is at least k. It is still open whether f(3) exists or not. The fractional version of the Erdős-Neumann-Lara conjecture was resolved by Bojan Mohar. This implies that the Erdős-Neumann-Lara conjecture only remains open for classes of graphs with bounded fractional chromatic numbers. In this project we wish to explore such classes in more detail. PART 2: Stable Approximation Algorithms Problem 3: We would also look to explore Stable Approximation Algorithms for various dynamic optimization problems which is described below. Broadly speaking, we have a Problem X (for example Independent Set). As the input objects (vertices of the graph, for instance) arrive and perhaps depart one by one over time, we try to maintain a solution alg(X) which is close to the optimal solution opt(X) without modifying alg(X) by a lot. Naively, after the arrival of a vertex, we can completely recompute a new optimal solution—note that we allow infinite computational power—but then the number of modifications (also referred to as stability) to alg can go very high, which is not desirable. In particular, we are interested in trade-offs between the stability of an algorithm and its approximation ratio. To quantify this, we define stable approximation schemes (SAS) below. Definition: A stable approximation scheme, or SAS for short, is an update algorithm alg that, for any given yet fixed positive ε, is k(ε)-stable and that maintains a solution with approximation ratio 1 + ε, where the stability parameter k(ε) only depends on ε and not on the size of the current input. There are several challenging open questions from my previous research on SAS that we wish to explore further.