A Progressive Search Algorithm for the Minimum Hitting Set Problem

Abstract

Given a finite universe and a collection of the subsets of the universe, the minimum hitting set of the collection is the smallest subset of the universe that has non-empty intersection with each set in the collection. Finding the minimum hitting set is an NP-Hard problem that has many real world applications. In this study, we propose a progressive search-based approach to find the minimum hitting set of a given collection. The algorithm starts searching for the hitting sets of size 1 and increase the expected size of the minimum hitting set by a factor of d. After each unsuccessful search, it increases the expected size by d and generate the candidate sets with the expected size. After each successful search, the algorithm takes the average of last unsuccessful and successful searches and continue the searching with the new expected size. The algorithm terminates when the detected upper bound coincides with the detected lower bound. The effect of different values for d on the performance of the algorithm has been experimented on various data sets. Experimental results reveal that the proposed method effectively computes the minimum hitting set on real-world data and random dataset.

Keywords

• Minimum Hitting Set
• NP-Hard Problems
• Progressive Search

Minimum İsabet Kümesi Problemi için Aşamalı Arama Algoritması

Abstract

Sonlu bir evren ve evrenin alt kümelerinin bir birleşimi verildiğinde, birleşimin minimum isabet kümesi, birleşimdeki her kümeyle boş olmayan kesişimi olan evrenin en küçük alt kümesidir. Minimum isabet kümesini bulma, birçok gerçek dünya uygulaması olan bir NP-Hard problemidir. Bu çalışmada, verilen bir birleşimin minimum isabet kümesini bulmak için aşamalı arama tabanlı bir yaklaşım öneriyoruz. Algoritma, boyutu 1 olan isabet kümelerini aramayla başlar ve minimum isabet kümesinin beklenen boyutunu d faktörü kadar artırır. Her başarısız aramadan sonra, algoritma beklenen boyutu d kadar artırır ve beklenen boyuta sahip aday kümeleri oluşturur. Her başarılı aramadan sonra, algoritma son başarısız ve başarılı aramaların ortalamasını alır ve yeni beklenen boyutla aramaya devam eder. Algılanan üst sınır, algılanan alt sınırla çakıştığı zaman algoritma sona erer. d faktörünün farklı değerlerinin algoritmanın performansı üzerindeki etkisi çeşitli veri kümeleri üzerinde denenmiştir. Deneysel sonuçlar, önerilen yöntemin gerçek dünya verileri ve rasgele veriler üzerindeki minimum isabet kümesini etkili bir şekilde hesapladığını ortaya koymaktadır.

Keywords

• Minimum İsabet Kümesi
• NP-Hard Problemler
• Aşamalı Arama

References

1. [1] Lin, L. and Jiang, Y. 2003. The computation of hitting sets: Review and new algorithms. In Information Processing Letters, 177-184.
2. [2] de Kleer, J. 2011. Hitting set algorithms for model-based diagnosis. In 22th International Workshop on Principles of Diagnosis (DX-11).
3. [3] Carastan-Santos, D., Camargo, R. Y., Martins, D. C., Song, S. W., and Rozante, L. C. S. 2017. Finding exact hitting set solutions for systems biology applications using heterogeneous GPU clusters. In Future Generation Computer Systems, 67:418-429.
4. [4] Liu, J., Xu, H. and Xie, C. 2007. A New Statistical Hitting Set Attack on Anonymity Protocols, In 2007 International Conference on Computational Intelligence and Security (CIS 2007), pp. 922-925, doi: 10.1109/CIS.2007.73.
5. [5] Bailey J., Stuckey P.J. (2005) Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization. In: Hermenegildo M.V., Cabeza D. (eds) Practical Aspects of Declarative Languages. PADL 2005. Lecture Notes in Computer Science, vol 3350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30557-6_14
6. [6] Kavvadias D.J., Stavropoulos E.C. (1999) Evaluation of an Algorithm for the Transversal Hypergraph Problem. In: Vitter J.S., Zaroliagis C.D. (eds) Algorithm Engineering. WAE 1999. Lecture Notes in Computer Science, vol 1668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48318-7_8
7. [7] Gainer-Dewar, A. and Vera-Licona, P. 2016. The Minimal Hitting Set Generation Problem: Algorithms and Computation, 31(1):63-100.
8. [8] Chan, T. M., Har-Peled, S. 2012. Approximation algorithms for maximum independent set of pseudo-disks. In Discrete Comput. Geom., 48 (2): 373-392.

9. [9] Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence, 32(1):57- 95.
10. [10] Wotawa, F. 2001. A variant of reiter's hitting-set algorithm. Information Processing Letters, 79(1):45-51.
11. [11] Pill, I.H. and Quaritsch, T. 2012. Optimizations for the boolean approach to computing minimal hitting sets. In Luc de Raedt, editor, ECAI 2012 - 20th European Conference on Arti cial Intelligence, 27{31 August 2012, Montpellier, France Including Prestigious Applications of Artificial Intelligence (PAIS-2012) System Demonstrations Track, volume 242 of Frontiers in Artificial Intelligence and Applications. 2012. Netherlands, 648-653.
12. [12] Zhao, X., and Ouyang, D. 2015. Deriving all minimal hitting sets based on join relation. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(7):1063-1076.
13. [13] Nyberg, M. 2011. A generalized minimal hitting-set algorithm to handle diagnosis with behavioral modes. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 41(1):137-148.
14. [14] Zhou, G., Feng, W., Jiang, B., Li, C. 2014. Computing minimal hitting set based on immune genetic algorithm. International Journal of Modelling, Identication and Control, 21(1):93-100. 2014.
15. [15] Liu, J., Ouyang, D.T., Wang, Y., Wang, Y. Zhang, L. 2015. Computing minimal hitting set based on immune genetic algorithm. Acta Electr. Sinica, 43(5):841-845.
16. [16] Hu, K., Liu, Z., Huang, K., Dai, C., Gao, S. 2016. Improved diferential evolution algorithm of model-based diagnosis in traction substation fault diagnosis of high-speed railway. IET Electrical Systems in Transportation, 6(3):163-169.
17. [17] Gao, S., Dai, C., Liu, Z., Geng, X. 2014. Geng. Application of bpso with ga in model-based fault diagnosis of traction substation. In 2014 IEEE Congress on Evolutionary Computation (CEC), 2063-2069.
18. [18] Wang, Q., Jin, T., Mohammed, M. A. 2019. An innovative minimum hitting set algorithm for model-based fault diagnosis in power distribution network. IEEE Access, 7:30683-30692.
19. [19] Ouali, M. E., Fohlin, H., Srivastav, A. 2014. A randomised approximation algorithm for the hitting set problem. In Theoretical Computer Science, 555:23-34.
20. [20] Frequent itemset mining dataset repository. http://fimi.cs.helsinki./data/, May accessed: 2020.