Research #

This page discusses (at a very basic level) some topics and problems I have been interested in over the past 15 years. If you would like to go further, you can have a glance at my Habilitation thesis (written in 2017).

Graph theory #

Graphs are mathematical objects describing how some elements in a set relate to each other. They can be used to model various real-world objects, such as networks (see below a graph modelling the tramway network in Grenoble), or molecules in chemistry and biology.

Classical optimization problems in these areas and in operation research have led to the introduction of fundamental problems in graph theory (colorings, matchings, flows, …). Some of them have turned out to be hard to solve (even with the most powerful computers), while some can be solved quickly in practice for graphs containing hundreds of thousands of elements.

The major problem is to understand what makes a problem easy or hard, and how the structure of graphs influences the difficulty of the problems we are trying to solve on them. Assume for instance that the graphs we are considering come from road networks, can we use this information to obtain better and faster algorithms to solve our problems, or to know in advance the properties of an optimal solution?

Combinatorial Optimization #

Two classical problems in combinatorial optimization are the Maximum Independent Set Problem, where the goal is to find the maximum number of pairwise non-adjacent vertices in a graph (see the red vertices in the left figure below), and the Maximum Matching Problem, where the goal is to find the maximum number of pairwise non-adjacent edges in a graph (see the red edges in the right figure below). The two problems look very similar but the first is hard, while the second is easy.

Another hard problem in the area is graph coloring, which dates back to a question asked by Francis Guthrie in 1852: can we color every map with 4 colors, in such a way that countries sharing a boarder always have different colors? The question was only solved much later (at the end of the 20th century), but graph coloring turned out to be important for real-world problems, such as scheduling.

Distributed algorithms #

Another area where coloring is fundamental is distributed computing. Here, computations are not run by a central authority, but by independent agents that can communicate with their neighbors, but do not have a global view of the network. A classical task before running a distributed algorithm is to break symmetries, and obtaining a coloring of the network (using a distributed procedure) is a good way to do that. The study of the power and limitation of distributed coloring algorithms (compared to their centralized counterparts) has nice connections with other areas of mathematics and computer science, such as the theory of expander graphs, or communication complexity.

Graphs in geometry and topology #

In many applications, the graphs modelling the problems carry some information about the geometry or topology of the original instances. This information can sometimes be used to obtain solutions of better quality, with faster algorithms. A typical example is the channel assignment problem for cell towers or radio antennas. The goal is to assign frequencies to each antenna such that neighboring antennas emit on different frequencies (to avoid interferences), while minimizing the total bandwidth (the number of frequencies). This is equivalent to coloring unit-disk graphs in the plane with the minimum number of colors.

When graphs have a geometric or topological structure, the techniques usually involve extracting structural properties of graphs using tools from geometry or topology. Fairly often, questions in geometric or topological graph theory translate into purely geometric or topological questions that are interesting in their own right.