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
DOI: https://doi.org/10.19139/soic-2310-5070-855
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
Issue
Vol 8 No 2 (2020)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).