Incremental complexity of a bi-objective hypergraph transversal problem

Ricardo Andrade (1, 2) , Etienne E. Birmelé (3) , Arnaud Mary (4) , Thomas Picchetti (3) , Marie-France Sagot (5, 1)

1 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
2 LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
3 MAP5 - UMR 8145 - Mathématiques Appliquées Paris 5
4 Baobab
5 Service d'Epidémiologie et de santé publique

The hypergraph transversal problem has been intensively studied, from both 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 (A, B), and the aim is to find minimal sets which hit all the hyperedges of A while intersecting a minimal set of hyperedges of B. In this paper, we formalize this problem, link it to a problem on monotone boolean ∧ − ∨ formulae of depth 3 and study its incremental complexity.

Mots clés: transversal; complexity; hypergraph

Domaines: Complexité [cs.CC]; Algorithme et structure de données [cs.DS]; Bio-informatique [q-bio.QM]

Ricardo Andrade, Etienne E. Birmelé, Arnaud Mary, Thomas Picchetti, Marie-France Sagot. Incremental complexity of a bi-objective hypergraph transversal problem. Fundamentals of Computation Theory (FCT2015), Aug 2015, Gdansk, Poland. pp.202-213, ⟨10.1007/978-3-319-22177-9_16⟩. ⟨hal-01149392⟩