5 citations · 15 across the 12 of their papers we have counts for
22 papers
A more versatile model for enumerative kernelization: a case study for Vertex Cover
Marin Bougeret, Guilherme C. M. Gomes, Ignasi Sau
Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kerne…
Kernelization dichotomies for hitting minors under structural parameterizations
Marin Bougeret, Eric Brandwein, Ignasi Sau
For a finite collection of connected graphs , the -MINOR-DELETION problem consists in, given a graph and an integer , deciding whether conta…
Enumeration kernels for Vertex Cover and Feedback Vertex Set
Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos +1
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creig…
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…
Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
Marin Bougeret, Bart M. P. Jansen, Ignasi Sau
For a fixed graph , the -SUBGRAPH HITTING problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of as a…
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…
Kernelization for Graph Packing Problems via Rainbow Matching
Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos +1
We introduce a new kernelization tool, called rainbow matching technique}, that is appropriate for the design of polynomial kernels for packing problems and their hitting counterpa…
Approximating optimization problems in graphs with locational uncertainty
Marin Bougeret, Jérémy Omer, Michael Poss
Many combinatorial optimization problems can be formulated as the search for a subgraph that satisfies certain properties and minimizes the total weight. We assume here that the ve…
Optimization problems in graphs with locational uncertainty
Marin Bougeret, Jérémy Omer, Michael Poss
Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the…
Parameterized complexity of computing maximum minimal blocking and hitting sets
Júlio Araújo, Marin Bougeret, Victor A. Campos +1
A blocking set in a graph is a subset of vertices that intersects every maximum independent set of . Let be the size of a maximum (inclusion-wise) minimal bl…
Introducing lop-kernels: a framework for kernelization lower bounds
Júlio Araújo, Marin Bougeret, Victor A. Campos +1
In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph and a positive integer , and the objective is to decide whether contains a minimal vertex cover…
Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
Marin Bougeret, Bart M. P. Jansen, Ignasi Sau
We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can redu…
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2
A knot in a directed graph is a strongly connected subgraph of with at least two vertices, such that no vertex in is an in-neighbor of a vertex in $V(G)\setminus…
Approximation results for makespan minimization with budgeted uncertainty
Marin Bougeret, Klaus Jansen, Michael Poss +1
We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which…
(Arc-disjoint) cycle packing in tournament: classical and parameterized complexity
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
Given a tournament , the problem MaxCT consists of finding a maximum (arc-disjoint) cycle packing of . In the same way, MaxTT corresponds to the specific case where the colle…
Triangle packing in (sparse) tournaments: approximation and kernelization
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
Given a tournament T and a positive integer k, the C_3-Pakcing-T problem asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tourna…
How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Marin Bougeret, Ignasi Sau
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsk{y} et a…
The complexity of partitioning into disjoint cliques and a triangle-free graph
Marin Bougeret, Pascal Ochem
Motivated by Chudnovsky's structure theorem of bull-free graphs, Abu-Khzam, Feghali, and Müller have recently proved that deciding if a graph has a vertex partition into disjoint c…
On independent set on B1-EPG graphs
Marin Bougeret, Stephane Bessy, Daniel Gonçalves +1
In this paper we consider the Maximum Independent Set problem (MIS) on -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersin…
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
Marin Bougeret, Guillerme Duvillié, Rodolphe Giroudeau +1
In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). An input of this problem is defined by disjoint…