Home
Benjamin Bergougnoux's picture

Benjamin Bergougnoux

Postdoctoral fellow

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.<br>Recently, I was able to obtain a single meta-algorithm which gives the best known algorithms for many width measures and many problems.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.