Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory

Abstract

It is known that there are many NP-hard and NP-complete problems in graph theory. The aim of this paper to prepare some basic methods for solving such problems (min dominating set, max independent set, max clique, etc.). In order to construct such fundamentals, the effectiveness and ineffectiveness of all nodes in the given graph are computed. Then these values will be used in solving NP-Hard problems of graphs.

Keywords

• Dominating Sets,Fundamental Cut-Sets,Efficient Algorithms,Independent Sets,Maximum Clique

Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory

Abstract

It is known that there are many NP-hard and NP-complete problems in graph theory. The aim of this paper to prepare some basic methods for solving such problems (min dominating set, max independent set, max clique, etc.). In order to construct such fundamentals, the effectiveness and ineffectiveness of all nodes in the given graph are computed. Then these values will be used in solving NP-Hard problems of graphs.

Keywords

• Dominating Sets,Fundamental Cut-Sets,Efficient Algorithms,Independent Sets,Maximum Clique

References

1. Alikhan, S., Peng, Y.-H., “Construction of Dominating Sets of Certain Graphs”, Journal of Discrete Mathematics, Vol:2013, Article ID:587196, 2013.
2. Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
3. Bresar, B., Movarraei, N., “On the number of maximal independent sets in minimum colorings of split graphs”, Discrete Applied Mathematics, Vol:247, pp:352-356, 2018.
4. Bron, C., Kerbosch, J.,”Algorithm 457: Finding all cliques of an undirected graph”, ACM Communication, Vol:16, pp:575-577, 1973. Connolly, S., Gabor, Z., Godbole, A., Kay, B., Kelly, T.,”Bounds on the Maximum Number of Minimum Dominating Sets”, Discrete Mathematics, Vol:339, pp:1537-1542, 2016.
5. Deng, Y.-P., Sun, Y.-Q., Liu, Q., Wang, H.-C.,”Efficient Dominating Sets in Circular Graphs”, Discrete Mathematics, Vol:340, pp:1503-1507, 2017.
6. Goddard, W., Henning, M.A., “Independent domination in Graphs: A Survey and Recent Results”, Discrete Mathematics, Vol: 313, pp:839-854, 2013.
7. Golovach, P.A., Heggernes, P., Kante, M.M., Kratsch, D., Villanger, Y.,”Enumerating Minimal Dominating Sets in Chordal Bipartite Graphs”, Discrete Applied Mathematics, Vol:199, pp:30-36, 2016.
8. Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.

9. Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
10. 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.
11. 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.
12. Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
13. 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.
14. Marti-Farre, J., Mora, M., Ruiz, J. L.,”Uniform Clutters and Dominating Sets of Graphs”, Discrete Applied Mathematics, Vol:263, pp:220-233, 2019.
15. Naude, K.A.,”Refined pivot selection for maximal clique enumeration in graphs”, Theoretical Computer Science, vol:613, pp:28-37, 2016. Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
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. Rooij, J.van, Bodlaender, H.L., “Exact algorithms for dominating set”, Discrete Applied Mathematics, Vol:159, pp:2147-2164, 2011.
18. 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.
19. Thulasiraman, K.KT., Arumugan, S., Brandstadt, A., Nishizeki, T., “Handbook of Graph Theory, Combinatorial Optimization and Algorithms”, CRC Press, Sendai, Japan, 2016.
20. 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.
21. 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.
22. Yu,T., Liu, M.,”a linear time algorithm for maximal clique enumeration in large sparse graphs”, Information Processing Letters, vol:125, pp:35-40, 2017.