Benjamin Bergougnoux

activity

20172025

most citedNew Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth

2 citations · 8 across the 11 of their papers we have counts for

collaborators

Showing 2022Show all

2 papers · 1 filter

cs.DS2022

Tight Lower Bounds for Problems Parameterized by Rank-width

Benjamin Bergougnoux, Tuukka Korhonen, Jesper Nederlof

We show that there is no $2^{o (k^{2})} n^{O (1)}$ time algorithm for Independent Set on $n$ -vertex graphs with rank-width $k$ , unless the Exponential Time Hypothesis (ETH) fails. Our…

cs.DS2022★ 1 cited

A logic-based algorithmic meta-theorem for mim-width

Benjamin Bergougnoux, Jan Dreier, Lars Jaffke

We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ( $A&C DN$ for short) which extends existential $MS O_{1}$ with…