Source author record

Benjamin Bergougnoux

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

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 all cycles containing a vertex of a given set. We design a meta-algorithm that allows to solve both problems in time $2^{O(rw^3)}\cdot n^{4}$ , $2^{O(q^2\log(q))}\cdot n^{4}$ , and $n^{O(k^2)}$ where $rw$ is the rank-width, $q$ the $\mathbb{Q}$ -rank-width, and $k$ the mim-width of a given decomposition. This answers in the affirmative an open question raised by Jaffke et al. (Algorithmica, 2019) concerning an XP algorithm for SFVS parameterized by mim-width. By a unified algorithm, this solves both problems in polynomial-time on the following graph classes: Interval, Permutation, and Bi-Interval graphs, Circular Arc and Circular Permutation graphs, Convex graphs, $k$ -Polygon, Dilworth- $k$ and Co- $k$ -Degenerate graphs for fixed $k$ ; and also on Leaf Power graphs if a leaf root is given as input, on $H$ -Graphs for fixed $H$ if an $H$ -representation is given as input, and on arbitrary powers of graphs in all the above classes. Prior to our results, only SFVS was known to be tractable restricted only on Interval and Permutation graphs, whereas all other results are new.

preprint2022arXiv

Recognition of Linear and Star Variants of Leaf Powers is in P

A $k$ -leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$ . A graph is a leaf power if it is a $k$ -leaf power for some $k$ . Over 20 years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when parameterized by $k$ , while leaving the main question open. In this paper, we explore this question from the perspective of two alternative models of leaf powers, showing that both a linear and a star variant of leaf powers can be recognized in polynomial-time.

preprint2020arXiv

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

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^{O(tw)}n^{O(1)}$ , for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time $2^{O(tw \log tw)}n^{O(1)}$ with tight lower bounds under the Exponential-Time Hypothesis (ETH), ruling out $2^{o(tw \log tw)}n^{O(1)}$ , where $n$ is the number of vertices and $tw$ is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no $2^{o(tw \log tw)}n^{O(1)}$ -time algorithm for Even Cycle Transversal under the ETH.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.