Benjamin Bergougnoux


Email: firstname.lastname(at)uib.no

Curriculum vitæ

I am currently a postdoc at the University of Bergen, my advisor is Jan Arne Telle.

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 that consists to study the complexity of computational problems one by one.
Width parameters such as tree-width, clique-width and twin-width are essential in this line of research. Intuitively, these parameters are associated with some way of recursively decomposing a graph into smaller graphs in a tree-like fashion. The width of a graph measures the simplicity of its best decomposition. 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.

Wonderful photo of myself

Publications (see also my dblp)

Click on the publication for more information (abstract, pdf, slides,...).

PhD Thesis

Some Links
This website uses Bootstrap 4, MathJax and Vue.js. Feel free to use the source code.