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, unless P = NP. The same question was left open for graphs, with only a few tractable cases known to date. In this paper, we focus on graph classes that capture incidence relations such as bipartite, co-bipartite, and split graphs, motivated by their strong relation with hypergraphs. Concerning maximal irredundant sets, we show that the problem on co-bipartite graphs is as hard as in general graphs and tractable in split and strongly orderable graphs, the latter being a generalization of chordal bipartite graphs. As for minimal redundant sets enumeration, we first show that the problem is intractable in split and co-bipartite graphs, answering the aforementioned open question. Then, we show that it is tractable on (C₃,C₅,C₆,C₈)-free graphs, a class of graphs incomparable to strongly orderable graphs, and which also generalizes chordal bipartite graphs. Our positive results rely on the structural properties of these graph classes and thus cannot be easily extended to bipartite graphs, for which the question remains open for both problems.

The incorporation of domain knowledge (DK) in AI has been studied for years and turns out to be critical in practice. Functions are also a basic notion for dealing with data science projects and are somehow related to DK. Consider the following scenario. Let \(D(y, z_1, \ldots , z_n)\) be a dataset, Alice a data scientist, Bob a domain expert and \(y = f(z_1, \ldots , z_n)\) a function known to Bob from his background knowledge. Alice is interested in the following simple yet crucial questions: How to define the satisfaction of f in D ? How to measure that satisfaction efficiently? How does this satisfaction relate to the supervised learning task of learning f from D ? It turns out that these problems are related to the study of counterexamples through the use of functional dependencies (FDs) and, in particular, FD measures used to quantify their satisfaction in a dataset such as the \(g_3\) indicator where the equality is replaced by more flexible predicates. In this article, we first examine the complexity of computing \(g_3\) . It is known that \(g_3\) can be computed in polynomial time when using equality, while it becomes NP -hard when using general predicates. Our goal is to refine this dichotomy by studying the impact of the following common properties: reflexivity, transitivity, symmetry, and antisymmetry. We show that symmetry and transitivity together are sufficient to guarantee that the \(g_3\) can be computed in polynomial time. However, removing one of them makes the problem NP -hard. Second, we study the computation of \(g_3\) in the polynomial and NP -hard cases identified previously. We propose different exact and approximate solutions for the computation of \(g_3\) in both cases. We compare these solutions in a detailed experimental study of time performance and approximation accuracy. All the algorithms are also made available via fastg3 , an open-source Python library with an underlying C++ implementation. Finally, we link counterexamples and \(g_3\) to supervised learning with a web application called adesit . adesit is intended to be part of an iterative data refinement process right after data selection and just before the machine learning process itself. It provides a way to evaluate the ability of a dataset to perform well for a given supervised learning problem through statistical and visual exploration. In a last section, we validate our approach by applying it to the industrial problem of air gap monitoring in compact hydro-generators.

International audience

Given a CNF formula $φ$ with clauses $C_1, \dots, C_m$ over a set of variables $V$, a truth assignment $\mathbf{a} : V \to \{0, 1\}$ generates a binary sequence $σ_φ(\mathbf{a})=(C_1(\mathbf{a}), \ldots, C_m(\mathbf{a}))$, called a signature of $φ$, where $C_i(\mathbf{a})=1$ if clause $C_i$ evaluates to 1 under assignment $\mathbf{a}$, and $C_i(\mathbf{a})=0$ otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNFs.

We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is $\mathbf{NP}$-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity.