Abstract
Let \(\mathcal{H}=(V,\mathcal{E})\) be a hypergraph with vertex set V and edge set \(\mathcal{E} \), where n : = |V| and \(m := |{\cal E}|\). Let l be the maximum size of an edge and Δ be the maximum vertex degree. A hitting set (or vertex cover) in \(\mathcal{H}\) is a set of vertices from V in which all edges are incident. The hitting set problem is to find a hitting set of minimum cardinality. It is known that an approximation ratio of l can be achieved easily. On the other side, for constant l, an approximation ratio better than l cannot be achieved in polynomial time under the unique games conjecture (Khot and Ragev 2008). Thus breaking the l-barrier for significant classes of hypergraphs is a complexity-theoretic and algorithmically interesting problem, which has been studied by several authors (Krivelevich (1997), Halperin (2000), Okun (2005)). We propose a randomised algorithm of hybrid type for the hitting set problem, which combines LP-based randomised rounding, graphs sparsening and greedy repairing and analyse it in different environments. For hypergraphs with \(\Delta = O(n^{\frac14})\) and \(l=O(\sqrt{n})\) we achieve an approximation ratio of \(l\left(1-\frac{c}{\Delta}\right)\), for some constant c > 0, with constant probability. In the case of l-uniform hypergraphs, l and Δ being constants, we prove by analysing the expected size of the hitting set and using concentration inequalities, a ratio of \(l\left(1-\frac{l-1}{4\Delta}\right)\). Moreover, for quasi-regularisable hypergraphs, we achieve an approximation ratio of \(l\left(1-\frac{n}{8m}\right)\). We show how and when our results improve over the results of Krivelevich, Halperin and Okun.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Alon, N., Moshkovitz, D., Safra, S.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms (ACM) 2, 153–177 (2006)
Alon, N., Spencer, J.: The probabilistic method, 2nd edn. Wiley Interscience (2000)
Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2, 198–203 (1981)
Bar-Yehuda, R., Even, S.: A local ratio theorem for approximating weighted vertex cover problem. In: Ausiello, G., Lucertini, M. (eds.) Analysis and Design of Algorithms for Combinatorial Problems. Annals of Discrete Math., vol. 25, pp. 27–46. Elsevier, Amsterdam (1985)
Berge, C.: Hypergraphs-combinatorics of finite sets. North Holland Mathematical Library (1989)
Chvatal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res. 4(3), 233–235 (1979)
Feige, U.: A treshold of ln n for approximating set cover. Journal of the ACM 45(4), 634–652 (1998)
Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms 41(2), 174–201 (2001)
Frieze, A., Jerrum, M.: Improved approximation algorithms for max k-cut and max bisection. Algorithmica 18, 67–81 (1997)
Füredi, Z.: Matchings and covers in hypergraphs. Graphs and Combinatorics 4(1), 115–206 (1988)
Gandhi, R., Khuller, S., Srinivasan, A.: Approximation Algorithms for Partial Covering Problems. J. Algorithms 53(1), 55–84 (2004)
Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In: ACM-SIAM Symposium on Discrete Algorithms, vol. 11, pp. 329–337 (2000)
Hochbaum, D.S.: Approximation algorithms for the set covering and vertex cover problems. SIAM J. Computation 11(3), 555–556 (1982)
Hall, N.G., Hochbaum, D.S.: A fast approximation for the multicovering problem. Discrete Appl. Math. 15, 35–40 (1986)
Jäger, G., Srivastav, A.: Improved approximation algorithms for maximum graph partitioning problems. Journal of Combinatorial Optimization 10(2), 133–167 (2005)
Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9, 256–278 (1974)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335–349 (2008)
Krivelevich, J.: Approximate set covering in uniform hypergraphs. J. Algorithms 25(1), 118–143 (1997)
Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383–390 (1975)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41, 960–981 (1994)
McDiarmid, C.: Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–248. Springer, Berlin (1998)
Peleg, D., Schechtman, G., Wool, A.: Randomized approximation of bounded multicovering problems. Algorithmica 18(1), 44–66 (1997)
Okun, M.: On approximation of the vertex cover problem in hypergraphs. Discrete Optimization (DISOPT) 2(1), 101–111 (2005)
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. on Theory of Computing, pp. 475–484 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
El Ouali, M., Fohlin, H., Srivastav, A. (2013). A Randomised Approximation Algorithm for the Hitting Set Problem. In: Ghosh, S.K., Tokuyama, T. (eds) WALCOM: Algorithms and Computation. WALCOM 2013. Lecture Notes in Computer Science, vol 7748. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36065-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-36065-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36064-0
Online ISBN: 978-3-642-36065-7
eBook Packages: Computer ScienceComputer Science (R0)