8 papers
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…
Generating minimal redundant and maximal irredundant sets in incidence graphs
Emanuel Castelo, Jérémie Chalopin, Oscar Defrain +1
It has been proved by Boros and Makino that there is no output-polynomial-time algorithm enumerating the minimal redundant sets or the maximal irredundant sets of a hypergraph, unl…
A quasi-optimal upper bound for induced paths in sparse graphs
Basile Couëtoux, Oscar Defrain, Jean-Florent Raymond
In 2012, NeÅ¡etÅil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order also have an induced path of order . In this paper…
Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
Marthe Bonamy, Oscar Defrain, Piotr Micek +1
Enumerating minimal transversals in a hypergraph is a notoriously hard problem. It can be reduced to enumerating minimal dominating sets in a graph, in fact even to enumerating min…
Translating between the representations of an acyclic convex geometry of bounded degree
Oscar Defrain, Arthur Ohana, Simon Vilmin
We consider the problem of translating between irreducible closed sets and implicational bases in closure systems. To date, the complexity status of this problem is widely open, an…
Parameterized complexity of isometric path partition: treewidth and diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth () of the input graph, arguably one of the most…