Globally Optimal Dense and Sparse Spanning Trees, and their Applications

  • Mustafa Ozen New Jersey Institute of Technology, Newark, NJ, 07102, USA
  • Goran Lesaja Georgia Southern University, USA
  • Hua Wang Georgia Southern University, Statesboro, Georgia
Keywords: Graphs, dense and sparse spanning trees, degree sequence, global optimization, genetic algorithm, discrete optimization, Kruskal’s algorithm.

Abstract

Finding spanning trees under various constraints is a classic problem with applications in many fields. Recently, a novel notion of dense ( sparse ) tree, and in particular spanning tree (DST and SST respectively), is introduced as the structure that have a large (small) number of subtrees, or small (large) sum of distances between vertices. We show that finding DST and SST reduces to solving the discrete optimization problems. New and efficient approaches to find such spanning trees is achieved by imposing certain conditions on the vertex degrees which are then used to define an objective function that is minimized over all spanning trees of the graph under consideration. Solving this minimization problem exactly may be prohibitively time consuming for large graphs. Hence, we propose to use genetic algorithm (GA) which is one of well known metaheuristics methods to solve DST and SST approximately. As far as we are aware this is the first time GA has been used in this context.We also demonstrate on a number of applications that GA approach is well suited for these types of problems both in computational efficiency and accuracy of the approximate solution. Furthermore, we improve the efficiency of the proposed method by using Kruskal s algorithm in combination with GA. The application of our methods to several practical large graphs and networks is presented. Computational results show that they perform faster than previously proposed heuristic methods and produce more accurate solutions. Furthermore, the new feature of the proposed approach is that it can be applied recursively to sub-trees or spanning trees with additional constraints in order to further investigate the graphical properties of the graph and/or network. The application of this methodology on the gene network of a cancer cell led to isolating key genes in a network that were not obvious from previous studies.

Author Biographies

Mustafa Ozen, New Jersey Institute of Technology, Newark, NJ, 07102, USA
Ph.D student at the New Jersey Institute of Technology. Expected to graduate in May 2020.
Goran Lesaja, Georgia Southern University, USA
Professor in the Department of mathematical Sciences at Georgia Southern University.
Hua Wang, Georgia Southern University, Statesboro, Georgia
Professor  in the Department of Mathematical Sciences at Georgia Southern University.

References

L. Gargano, P. Hell, L. Stacho, and U. Vaccaro, Spanning trees with bounded number of branch vertices,In 29th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, Springer, Berlin, 2380, pp. 355–365, 2002.

R. Silva, D. Silva, M. Resende, G. Mateus, J. Goncalves, and P. Festa, An edge-swap heuristic for generating spanning trees with minimum number of branch vertices, Optim. Lett. vol. 8, pp. 1225–1243, 2014.

C. Bazlamacci, and K. Hindi, Minimum-weight spanning tree algorithms: A survey and empirical study, Computers and Operations Research, vol. 28, pp. 767–785, 2001.

F. K. Hwang, D. S. Richards, and P. Winter, The steiner tree problem, North-Holland, New York, 1992.

S. C. Narula, and C. A. Ho, Degree-constrained minimum spanning tree, Comput. Oper. Res., vol. 7, pp. 239–249, 1980.

M. Ozen, H. Wang, K. Wang, and D. Yalman, An edge-swap heuristic for finding dense spanning trees, Theory Appl. Graphs., vol. 3, no. 1, pp. 1–10, 2016.

A. Darmann, U. Pferschy, and J. Schauer, Minimal spanning trees with conflict graphs, Optimization online, 2009.

A. Amberg,W. Domschke, S. Voss, S. Vo, Capacitated minimum spanning trees: algorithms using intelligent search, Combinatorial Optimization: Theory and Practice 1, pp. 9–40, 1996.

T. Li, Y. Gao, Q. Dong, and H. Wang, Degree sums and dense spanning trees, PLoS ONE, vol. 12, no. 9, 2017.

H. Wiener, Structural determination of paraffin boiling points J. Am. Chem. Soc., vol. 69, pp. 17–20, 1947.

H. Wiener, Correlation of heats of isomerization, and differences in heats of vaporization of isomers among the paraffin hydrocarbons, J. Am. Chem. Soc., vol. 69, pp. 2636–2638, 1947.

L. A. Sz´ekely, and H. Wang, On subtrees of trees, Adv. Appl. Math., vol. 34, pp. 138–155, 2005.

S. Wagner, Correlation of graph-theoretical indices, SIAM J. Discrete Mathematics, vol. 21, no. 1, pp. 33–46, 2007.

N. Schmuck, S.Wagner, and H.Wang, Greedy trees, caterpillars, andWiener-type graph invariants, MATCH Commun.Math.Comput.Chem., vol. 68, no. 1, pp. 273–292, 2012.

H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Applied Mathematics, vol. 156, pp. 2647–2654, 2008.

X. D. Zhang, Q. Y. Xiang, L. Q. Xu, and E. Y. Pan, The Wiener index of trees with given degree sequences, MATCH Commun.Math.Comput.Chem., vol. 60, pp. 623–644, 2008.

X. M. Zhang, X. D. Zhang, D. Gray, and H. Wang, The number of subtrees of trees with given degree sequence, J. Graph Theory, vol. 73, no. 3, pp. 280–295, 2013.

M. Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996.

MathWorks: Global optimization toolbox: User’s guide (R2018b). Retrieved Sept 17, 2018 from https://www.mathworks.com/help/pdf_doc/gads/gads_tb.pdf

J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, vol. 7, pp. 48–50, 1956.

T. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, MIT Press (3rd ed.), Cambridge, MA, 2009.

IBM ILOG CPLEX Optimization Studio, Retrieved Jan 18, 2020 from https://www.ibm.com/products/ilog-cplex-optimization-studio

A. R. Rossi, and N. K. Ahmed, The network data repository with interactive graph analytics and visualization, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence 2015, http://networkrepository.com

M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Physical review E, vol. 74, no. 3, 2006.

R. A. Rossi, D. F. Gleich, A. H. Gebremedhin, and M. A. Patwary, What if clique were fast? Maximum cliques in information networks and strong components in temporal networks, arXiv preprint arXiv:1210.5802, pp. 1–11, 2012.

Published
2020-05-27
How to Cite
Ozen, M., Lesaja, G., & Wang, H. (2020). Globally Optimal Dense and Sparse Spanning Trees, and their Applications. Statistics, Optimization & Information Computing, 8(2), 328-345. https://doi.org/10.19139/soic-2310-5070-855
Section
Research Articles