Optimal algorithms and data structures for decomposing graphs by small cuts and separators

Graphs are structures consisting of vertices (points) and edges (lines connecting pairs of points).

Graphs can model systems such as road networks (intersections connected by roads), social networks (people connected by friendships), and the internet (computers connected by data links). The design of efficient algorithms for processing graphs is a classic area in computer science.

However, there are still fundamental graph problems for which optimal algorithms remain undiscovered.This project aims to design optimal algorithms and data structures for solving graph problems related to finding small cuts or separators and decomposing graphs accordingly.

A basic example of a graph problem where I aim to advance the state-of-the-art is: Given a graph, determine whether it can be disconnected by removing at most 10 edges.

The best-known algorithm runs in near-linear O(n log n + m) time, while the goal of this project is to obtain a linear-time O(n+m) algorithm, which is optimal.

The specific number 10 is not important; rather, the goal is to develop a linear-time algorithm for any fixed value, in the spirit of parameterized algorithms.The research objectives are (1) to develop a linear-time algorithm for computing the k-edge-connected components of a graph, (2) to create an improved dynamic data structure for treewidth, and (3) to design a linear-time preprocessing algorithm for computing treewidth.

Objective (1) addresses a long-standing open problem in graph algorithms, while objectives (2) and (3) will significantly advance the state-of-the-art in key problems within parameterized algorithms.

I believe I have identified a feasible approach to tackling these problems, introducing new techniques from structural graph theory into algorithm design.Solving a key open problem in graph algorithms using tools from parameterized algorithms and structural graph theory will unify these fields and expand my professional network, significantly enhancing my career prospects.