2 citations · 8 across the 11 of their papers we have counts for
17 papers
Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
Benjamin Bergougnoux, Lars Jaffke
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided togethe…
Mim-Width is paraNP-complete
Benjamin Bergougnoux, Édouard Bonnet, Julien Duron
We show that it is NP-hard to distinguish graphs of linear mim-width at most 1211 from graphs of sim-width at least 1216. This implies that Mim-Width, Sim-Width, One-Sided Mim-Widt…
Enumerating minimal solution sets for metric graph problems
Benjamin Bergougnoux, Oscar Defrain, Fionn Mc Inerney
Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact in parameterized complexity by being the first…
Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
Emmanuel Sam, Benjamin Bergougnoux, Petr A. Golovach +1
For a given graph , a depth-first search (DFS) tree of is an -rooted spanning tree such that every edge of is either an edge of or is between a \textit{descen…
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
Benjamin Bergougnoux, Tuukka Korhonen, Igor Razgon
We study the tractability of the maximum independent set problem from the viewpoint of graph width parameters, with the goal of defining a width parameter that is as general as pos…