Benjamin Bergougnoux


Email: firstname.lastname(at)uib.no

Curriculum vitæ

I am currently working with Jan Arne Telle as a postdoc at the University of Bergen. The goal of this postdoc is study the complexity of computationally hard problems that can build the foundation for next generation asymmetric crypto algorithms.

Wonderful photo of myself

Research interests

I am fascinated by NP-hard problems ever since I have heard of them. My research interests dwell in the following question.

What structural restrictions make NP-hard problems tractable?

If we want a better understanding of their hardness, we need to find general answers at this question. We should avoid as far as possible the tedious approach which consists to study each problems and each instances classes separately.
In this line of research, parameterized complexity theory is a great toolkit. I am particularly interested by width-measures: a family of graph parameter based on the well-known divide and conquer paradigm. The most famous width-measures are tree-width, clique-width, rank-width and mim-width. These structural parameters have plenty of structural properties and algorithmic applications. Thank to them, we are able to explain the tractability of many NP-hard problems on plenty of structural restrictions. They allow to adopt very general approaches as illustrated by Courcelle's meta theorem.

Recently, I was able to obtain a single meta-algorithm which gives the best known algorithms for many width measures and many problems (see this article). This proves that we can adopt a general approach when we design efficient algorithms parameterized by width measures without looking at each width measure and each problem separately. I am currently trying to extend this approach to other kind of problems, lastly I was able to use it on Subset Feedback Vertex Set (see this article).

Wonderful photo of myself

Publications. Click on for more informations (abstract, pdf, slides,...).

PhD Thesis

Matrix Decompositions and Algorithmic Applications to (Hyper)Graphs

Université Clermont Auvergne. Defended on the 13th February 2019.
Some Links
Everything should be public: science most of all. This website uses Bootstrap 4 and Vue.js. Feel free to use the source.