Hardness of set cover with intersection 1. (English) Zbl 0973.68080

Montanari, Ugo (ed.) et al., Automata, languages and programming. 27th international colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1853, 624-635 (2000).
Summary: We consider a restricted version of the general set covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the set covering problem with intersection 1 cannot be approximated within a \(o(\log n)\) factor in random polynomial time unless \(\text{NP} \subseteq \text{ZTIME} (n^{O(\log\log n)})\). We also observe that the main challenge in derandomizing this reduction lies in finding a hitting set for large volume combinatorial rectangles satisfying certain intersection properties. These properties are not satisfied by current methods of hitting set construction.
An example of a set covering problem with the intersection 1 property is the problem of covering a given set of points in two or higher dimensions using straight lines; any two straight lines intersect in at most one point. The best approximation algorithm currently known for this problem has an approximation factor of \(\theta(\log n)\), and beating this bound seems hard. We observe that this problem is Max-SNP-Hard.
For the entire collection see [Zbl 0941.00034].


68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68W25 Approximation algorithms