5 papers · 1 filter
Tight Lower Bounds for Problems Parameterized by Rank-width
Benjamin Bergougnoux, Tuukka Korhonen, Jesper Nederlof
We show that there is no time algorithm for Independent Set on -vertex graphs with rank-width , unless the Exponential Time Hypothesis (ETH) fails. Our…
On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes +2
The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine…
Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time , for F…
Counting Minimal Transversals of -Acyclic Hypergraphs
Benjamin Bergougnoux, Florent Capelli, Mamadou Moustapha Kanté
We prove that one can count in polynomial time the number of minimal transversals of -acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal…
On Minimum Connecting Transition Sets in Graphs
Thomas Bellitto, Benjamin Bergougnoux
A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the g…