1 citations · 2 across the 16 of their papers we have counts for
25 papers
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud +2
We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer and a simple, undirected, and unweighted graph , the objective…
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…
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…
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 we…
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…
Enumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with t…
On the enumeration of signatures of XOR-CNF's
Nadia Creignou, Oscar Defrain, Frédéric Olive +1
Given a CNF formula with clauses over a set of variables , a truth assignment generates a binary sequence $σ_φ(\mathbf{a})=(C…
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…
Enumerating minimal solution sets for metric graph problems
Benjamin Bergougnoux, Oscar Defrain, Fionn Mc Inerney
Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact in parameterized complexity by being the first…
On the hardness of inclusion-wise minimal separators enumeration
Caroline Brosse, Oscar Defrain, Kazuhiro Kurita +3
Enumeration problems are often encountered as key subroutines in the exact computation of graph parameters such as chromatic number, treewidth, or treedepth. In the case of treedep…
Hypergraph dualization with FPT-delay parameterized by the degeneracy and dimension
Valentin Bartier, Oscar Defrain, Fionn Mc Inerney
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called ordered generation that yields an -delay algorithm listing all minimal transversals of an -vertex…
Sparse graphs without long induced paths
Oscar Defrain, Jean-Florent Raymond
Graphs of bounded degeneracy are known to contain induced paths of order when they contain a path of order , as proved by Nešetřil and Ossona de Mendez (2012).…
On digraphs without onion star immersions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
The -onion star is the digraph obtained from a star with leaves by replacing every edge by a triple of arcs, where in triples we orient two arcs away from the center, a…
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Laurent Beaudou, Caroline Brosse, Oscar Defrain +4
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_…
On Vizing's edge colouring question
Marthe Bonamy, Oscar Defrain, Tereza Klimošová +2
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a se…
Close relatives (of Feedback Vertex Set), revisited
Hugo Jacob, Thomas Bellitto, Oscar Defrain +1
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a $2^{o(k \log k)} \cdo…
On objects dual to tree-cut decompositions
Łukasz Bożyk, Oscar Defrain, Karolina Okrasa +1
Tree-cut width is a graph parameter introduced by Wollan that is an analogue of treewidth for the immersion order on graphs in the following sense: the tree-cut width of a graph is…
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…
Avoidable paths in graphs
Marthe Bonamy, Oscar Defrain, Meike Hatzel +1
We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k. Avoidability generalises th…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
Translating between the representations of a ranked convex geometry
Oscar Defrain, Lhouari Nourine, Simon Vilmin
It is well known that every closure system can be represented by an implicational base, or by the set of its meet-irreducible elements. In Horn logic, these are respectively known…
On the dualization in distributive lattices and related problems
Oscar Defrain, Lhouari Nourine, Takeaki Uno
In this paper, we study the dualization in distributive lattices, a generalization of the well-known hypergraph dualization problem. We in particular propose equivalent formulation…
Dualization in lattices given by implicational bases
Oscar Defrain, Lhouari Nourine
It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless P=NP. In this paper, we~show that this result ho…
Enumerating minimal dominating sets in -free graphs and variants
Marthe Bonamy, Oscar Defrain, Marc Heinrich +2
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph cl…