Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory

Abstract

The maximum independent set problem is an NP-complete problem in graph theory. The Karci Algorithm is based on fundamental cut-sets of given graph, and node with minimum independence values are selected for maximum independent set. In this study, the analytical verification of this algorithm for some special graphs was analysed, and the obtained results were explained. The verification of Karci’s Algorithm for maximum independent set was handled in partial.

Keywords

• Maximum Independent Set
• Karci Algorithm
• NP-Complete

References

1. Karci, A.,”New Algorithms for Minimum Dominating Set in Any Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:62-70, 2020a.
2. Karci, A.,” Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:137-143, 2020b.
3. Karci, A.,” Efficient Algorithms for Determining the Maximum Independent Sets in Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:144-149, 2020c.
4. Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
5. Karci, Ş., Ari, A., Karci, A.,” Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma”, Journal of the Faculty of Engineering and Architecture of Gazi University (accepted).
6. Baraji, S., Swaminathan, V., Kannan, K.,”A simple algorithm to optimize maximum independent set”, Advanced Modeling and Optimization, vol:12, Issue:1, pp:107-118, 2010.
7. Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
8. Lin, M.-S.,”Counting independent sets and maximal independent sets in some subclasses of bipartite graphs”, Discrete Applied Mathematics, Vol:251, pp:236-244, 2018a.

9. Laflamme, C., Aranda, A., Soukup, D.T., Woodrow, R.,”Balanced independent sets in graphs omitting large cliques”, Journal of Combinatorial Theory, Series B, Vol:137, pp:1-9, 2019.
10. Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
11. Wan, P., Tu, J., Zhang, S., Li, B., “Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth”, Applied Mathematics and Computation, Vol:332, pp:42-47, 2018.
12. Lin, M.-S., Chen, C.-M.,”Linear-time algorithms for counting independent sets in bipartite permutation graphs”, Information Processing Letters, Vol:122, pp:1-7, 2017.
13. Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
14. Sah, A., Sawhhney, M., Stoner, D., Zhao, Y.,”The number of independent sets in an irregular graph”, Journal of Combinatorial Theory, Series B, Vol:138, pp:172-195, 2019.
15. Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
16. Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
17. Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., Emmert-Streib, F.,”On graph entropy measures based on the number of independent sets and matchings”, Information Sciences, Vol:516, pp:491-504, 2020.