Blar i Bergen Open Research Archive på forfatter "Bergougnoux, Benjamin"
-
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
Bergougnoux, Benjamin; Bonnet, Édouard; Brettell, Nick; Kwon, O-Joung (Journal article; Peer reviewed, 2020)The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ... -
More Applications of the d-Neighbor Equivalence: Acyclicity and Connectivity Constraints
Bergougnoux, Benjamin; Kanté, Mamadou Moustapha (Journal article; Peer reviewed, 2021)In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced ... -
Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-Width
Bergougnoux, Benjamin; Papadopoulos, Charis; Telle, Jan Arne (Journal article; Peer reviewed, 2022)The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects ... -
On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters
Høgemo, Svein; Bergougnoux, Benjamin; Brandes, Ulrik; Paul, Christophe; Telle, Jan Arne (Journal article; Peer reviewed, 2021)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 in general, linear-time algorithms exist ... -
Towards a Polynomial Kernel for Directed Feedback Vertex Set
Bergougnoux, Benjamin; Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian; Ramanujan, M. S. (Journal article; Peer reviewed, 2020)In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...