Exploiting graph structure to beat brute-force search

A diverse collection of optimization problems on networks can be phrased in the mathematical framework of graph theory. The Graph Algorithms group investigates how to exploit structural properties of graphs to develop provably efficient algorithms for hard combinatorial problems.

Algorithmic graph theory is a fascinating field of research. It challenges us to capture the properties of real-world networks in mathematical terms and exploit that structure to compute optimal solutions while avoiding brute-force search. This leads to beautiful mathematical problems, involving diverse approaches such as cops-and-robber games, crossing-free drawings of graphs, logic, and extremal structure theory. The solutions to these elegant problems have the potential to yield algorithms that are applicable in a wide variety of applications.

The Graph Algorithms group targets fundamental NP-hard optimization problems on graphs, with the goal of determining which parameters of a problem input control the difficulty of solving it optimally. The research done in the group therefore falls in the realm of parameterized algorithmics, an expanding subfield of algorithm design with a strong emphasis on graph problems. Graph parameters that represent a decomposition of the input graph into simpler pieces form a frequent topic of investigation. In addition to developing exact algorithms that are provably efficient on inputs in which a suitable complexity parameter is small, the group also works on preprocessing algorithms (kernelization) and other means to reduce the search space of algorithms solving NP-hard problems.

While the primary focus in the group is on theoretical research, practical applications are explored through master’s thesis projects. A successful series of projects deployed graph algorithms for the Steiner Tree problem to compute cost-efficient plans to install fiber-optic networks in urban areas.