Incremental complexity of a bi-objective hypergraph transversal problem

The hypergraph transversal problem has been intensively studied, both from a theoretical and a practical point of view. In particular, its incremental complexity is known to be quasi-polynomial in general and polynomial for bounded hypergraphs. Recent applications in computational biology however require to solve a generalization of this problem, that we call bi-objective transversal problem. The instance is in this case composed of a pair of hypergraphs \((\mathcal {A},\mathcal {B})\), and the aim is to enumerate minimal sets which hit all the hyperedges of \(\mathcal {A}\) while intersecting a minimal set of hyperedges of \(\mathcal {B}\). In this paper, we formalize this problem and relate it to the enumeration of minimal hitting sets of bundles. We show cases when under degree or dimension contraints these problems remain NP-hard, and give a polynomial algorithm for the case when \(\mathcal {A}\) has bounded dimension, by building a hypergraph whose transversals are exactly the hitting sets of bundles.