7 papers · 1 filter
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…
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…
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…