AbstractA coloring of a hypergraph is a mapping of vertices to colors such that no hyperedge is monochromatic. We are interested in the problem of coloring 2-colorable hypergraphs. For the special case of graphs (hypergraphs of dimension 2) this can easily be done in linear time. The problem for general hypergraphs is much more difficult since a result of Lovàsz implies that the problem is NP-hard even if all hyperedges have size three.
In this paper we develop approximation algorithms for this problem. Our first result is an algorithm that colors any 2-colorable hypergraph on n vertices and dimension d with O(n^{1-1/d} log^{1-1/d}n) colors. This is the first algorithm that achieves a sublinear number of colors in polynomial time. This algorithm is based on a new technique for reducing degrees in a hypergraph that should be of independent interest. For the special case of hypergraphs of dimension three we improve on the previous result by obtaining an algorithm that uses only O(n2/9 log 17 / 8 n) colors. This result makes essential use of semidefinite programming. We further show that the semidefinite programming approach fails for larger dimensions.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]
Additional Key Words and Phrases: approximation algorithms, hypergraphs, semidefinite programming
Selected references
- Avrim Blum. New approximation algorithms for graph coloring. Journal of the ACM, 41(3):470-516, May 1994.
- Michel X. Goemans and David P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422-431, Montréal, Québec, Canada, 23-25 May 1994.
- David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. In 35th Annual Symposium on Foundations of Computer Science, pages 2-13, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- Sanjeev Mahajan and H. Ramesh. Derandomizing semidefinite programming based approximation algorithms. In 36th Annual Symposium on Foundations of Computer Science, pages 162-169, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Avi Wigderson. Improving the performance guarantee for approximate graph coloring. Journal of the ACM, 30(4):729-735, October 1983.