Source author record

Marin Bougeret

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 Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph $G$ and a parameter $k$ , one has to decide if there is a set $S$ of at most $k$ vertices such that $G-S$ is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time $2^{o(k)}n^{\mathcal{O}(1)}$ in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such $2^{o(k)}n^{\mathcal{O}(1)}$ algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time $2^{k^\varepsilon} \mathop{\rm poly}(n)$ , for some $\varepsilon<1$ , where $n$ denotes the number of vertices of the instance and $k$ the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of ``thin'' objects like segment graphs or more generally $s$ -string graphs.

preprint2021arXiv

Parameterized complexity of computing maximum minimal blocking and hitting sets

A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$ . Let ${\sf mmbs}(G)$ be the size of a maximum (inclusion-wise) minimal blocking set of $G$ . This parameter has recently played an important role in the kernelization of Vertex Cover parameterized by the distance to a graph class ${\cal F}$ . Indeed, it turns out that the existence of a polynomial kernel for this problem is closely related to the property that ${\sf mmbs}({\cal F})=\sup_{G \in {\cal F}}{\sf mmbs}(G)$ is bounded by a constant, and thus several recent results focused on determining ${\sf mmbs}({\cal F})$ for different classes ${\cal F}$ . We consider the parameterized complexity of computing ${\sf mmbs}$ under various parameterizations, such as the size of a maximum independent set of the input graph and the natural parameter. We provide a panorama of the complexity of computing both ${\sf mmbs}$ and ${\sf mmhs}$ , which is the size of a maximum minimal hitting set of a hypergraph, a closely related parameter. Finally, we consider the problem of computing ${\sf mmbs}$ parameterized by treewidth, especially relevant in the context of kernelization. Given the "counting" nature of ${\sf mmbs}$ , it does not seem to be expressible in monadic second-order logic, hence its tractability does not follow from Courcelle's theorem. Our main technical contribution is a fixed-parameter tractable algorithm for this problem.

preprint2015arXiv

On independent set on B1-EPG graphs

In this paper we consider the Maximum Independent Set problem (MIS) on $B_1$ -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersinglebend} as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$ -EPG denotes EPG-graphs where every path has at most $k$ bends. The study of MIS on $B_1$ -EPG graphs has been initiated in~\cite{wadsMIS} where authors prove that MIS is NP-complete on $B_1$ -EPG graphs, and provide a polynomial $4$ -approximation. In this article we study the approximability and the fixed parameter tractability of MIS on $B_1$ -EPG. We show that there is no PTAS for MIS on $B_1$ -EPG unless P $=$ NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most $3$ . This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on $B_1$ -EPG restricted to only three shapes of path, and $W_1$ -hard on $B_2$ -EPG. The status for general $B_1$ -EPG (with the four shapes) is left open.

preprint2015arXiv

The complexity of partitioning into disjoint cliques and a triangle-free graph

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 cliques and a triangle-free graph is NP-complete for five graph classes. The problem is trivial for the intersection of these five classes. We prove that the problem is NP-complete for the intersection of two subsets of size four among the five classes. We also show NP-completeness for other small classes, such as graphs with maximum degree 4 and line graphs.

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.