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.

Academic article
  • Show author(s) 2020. Towards a Polynomial Kernel for Directed Feedback Vertex Set. Algorithmica. 21 pages.
  • Show author(s) 2020. Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth. Leibniz International Proceedings in Informatics. 3:1-3:17.
  • Show author(s) 2019. An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width. Algorithmica.
Academic chapter/article/Conference paper
  • Show author(s) 2020. Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width.

More information in national current research information system (CRIStin)