1 citations · 1 across the 3 of their papers we have counts for
6 papers
Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1
The neighbourhood complexity of a graph is a quantity measuring, for a graph and an integer , the maximum possible number (over all vertex subsets of size…
Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph and a parameter , one has to decide if there is a set of at most $…
Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Tri…
Kick the cliques
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
In the -Cover problem, given a graph and an integer one has to decide if there exists a set of at most vertices whose removal destroys all -cliques of . In t…
Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
In this paper we investigate the existence of subexponential parameterized algorithms of three fundamental cycle-hitting problems in geometric graph classes. The considered problem…
The complexity of L(p,q)-Edge-Labelling
Gaetan Berthe, Barnaby Martin, Daniel Paulusma +1
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially class…