Local Computation Algorithms for Fundamental Graph Problems

I will be investigating efficient local computation algorithms for various fundamental graph problems, such as the maximum matching problem and maximum independent set problem. This work falls under the research area of Theoretical Computer Science. A key focus of this research will be investigating algorithms that can be implemented in a distributed setting, where centralised computation is not feasible.

This research is important for a multitude of reasons. The first of which is that fundamental graph problems are abstract problems and have wide applications in many areas such as resource allocation for both economics and networking. The second reason is that, as datasets grow larger with advances in data storage and collection, there is a growing need for efficient distributed algorithms of this nature.

There is currently a large body of existing research in this area, although there are still many open problems yet to be solved and advances are being made as recently as last year in the field. My primary goal for this project is to push existing theory and contribute positively to this body of research. I want to look at whether there are any practical optimisations that can be made to existing cutting-edge algorithms to improve their performance.

I will begin by familiarising myself with the Centralised and Distributed LCA models, which capture many fundamental properties of distributed, local and streaming algorithms. Once this is done, I will explore existing cutting-edge algorithms and data structures with the aim of finding key insights for where optimisations and improvements could be made.

The results I investigate will primarily be theoretical, although I may also consider running some quantitative analysis on my findings if the need arises. Care should be taken in this case to ensure that the asymptotic behaviour is captured correctly and no systematic bias is involved.