TY - JOUR

T1 - Polynomial-time dualization of r-exact hypergraphs with applications in geometry

AU - Elbassioni, Khaled

AU - Rauf, Imran

PY - 2010/9/28

Y1 - 2010/9/28

N2 - Let H⊆2V be a hypergraph on vertex set V. For a positive integer r, we call Hr-exact if any minimal transversal of H intersects any hyperedge of H in at most r vertices. This class includes several interesting examples from geometry, e.g., circular-arc hypergraphs (r=2), hypergraphs defined by sets of axis parallel lines stabbing a given set of α-fat objects (r=4α), and hypergraphs defined by sets of points contained in translates of a given cone in the plane (r=2). For constant r, we give a polynomial-time algorithm for the duality testing problem of a pair of r-exact hypergraphs. This result implies that minimal hitting sets for the above geometric hypergraphs can be generated in output polynomial time.

AB - Let H⊆2V be a hypergraph on vertex set V. For a positive integer r, we call Hr-exact if any minimal transversal of H intersects any hyperedge of H in at most r vertices. This class includes several interesting examples from geometry, e.g., circular-arc hypergraphs (r=2), hypergraphs defined by sets of axis parallel lines stabbing a given set of α-fat objects (r=4α), and hypergraphs defined by sets of points contained in translates of a given cone in the plane (r=2). For constant r, we give a polynomial-time algorithm for the duality testing problem of a pair of r-exact hypergraphs. This result implies that minimal hitting sets for the above geometric hypergraphs can be generated in output polynomial time.

KW - Enumeration algorithms

KW - Geometric hitting sets

KW - Hypergraphs

KW - Transversals

UR - http://www.scopus.com/inward/record.url?scp=77954177828&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2010.05.017

DO - 10.1016/j.disc.2010.05.017

M3 - Article

AN - SCOPUS:77954177828

SN - 0012-365X

VL - 310

SP - 2356

EP - 2363

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 17-18

ER -