Transversal hypergraphs and families of polyhedral cones (Q2768039)

Let \(\mathcal K\) be a set of rational cones, while \(b\) be a rational \(n\)-vector in their sum. Let \(\text{MIN} ({\mathcal K},b)\) denotes the family of all minimum sets of cones which also contains \(b\). Similarly \(\text{MAX} ({\mathcal K},b)\) denotes the family of maximum set of cones which avoids \(b.\) The main results are that generating both families are NP-hard even for dihedral cones. The problem where all elements of \(\mathcal K\) are rays remains open. On the other hand for any sets of rational cones generating the union of the two families is polynomially equivalent to the hypergraph transversal problem, hence can be carried out in a quasi-polynomial time.NEWLINENEWLINEFor the entire collection see [Zbl 0968.00020].