Incremental complexity of a bi-objective hypergraph transversal problem

DOI10.1007/978-3-319-22177-9_16MaRDI QIDQ2947881zbMATH OpenOpenAlexFDO

Authors R. Andrade, Etienne Birmelé, Arnaud Mary, Thomas Picchetti, Marie-France Sagot

Publication date 29 September 2015

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.06025

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 $land$ -- $lor$ formulae of depth 3 and study its incremental complexity.

Recommendations

• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• Computing and Combinatorics
• scientific article; zbMATH DE number 1670855
• Identifying the Minimal Transversals of a Hypergraph and Related Problems

Cited in

(1)

• Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover

This page was built for publication: Incremental complexity of a bi-objective hypergraph transversal problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947881)