×

Computational approaches for zero forcing and related problems. (English) Zbl 1403.90566

Summary: In this paper, we propose computational approaches for the zero forcing problem, the connected zero forcing problem, and the problem of forcing a graph within a specified number of timesteps. Our approaches are based on a combination of integer programming models and combinatorial algorithms and include formulations for zero forcing as a dynamic process, and as a set-covering problem. We explore several solution strategies for these models, test them on various types of graphs, and show that they are competitive with the state-of-the-art algorithm for zero forcing. Our proposed algorithms for connected zero forcing and for controlling the number of zero forcing timesteps are the first general-purpose computational methods for these problems, and are superior to brute force computation.

MSC:

90C27 Combinatorial optimization
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aazami, A. (2008). Hardness results and approximation algorithms for some problems on graphs. Ph.D. thesis, University of Waterloo.; Aazami, A. (2008). Hardness results and approximation algorithms for some problems on graphs. Ph.D. thesis, University of Waterloo.
[2] Aazami, A., Domination in graphs with bounded propagation: algorithms, formulations and hardness results, Journal of Combinatorial Optimization, 19, 4, 429-456, (2010) · Zbl 1192.90215
[3] Ackerman, E.; Ben-Zwi, O.; Wolfovitz, G., Combinatorial model and bounds for target set selection, Theoretical Computer Science, 411, 44-46, 4017-4022, (2010) · Zbl 1235.90168
[4] Amos, D.; Caro, Y.; Davila, R.; Pepper, R., Upper bounds on the k-forcing number of a graph, Discrete Applied Mathematics, 181, 1-10, (2015) · Zbl 1304.05041
[5] Avella, P.; Boccia, M.; Vasilyev, I., Computational experience with general cutting planes for the set covering problem, Operations Research Letters, 37, 16-20, (2009) · Zbl 1154.90603
[6] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Applied Mathematics, 65, 21-46, (1996) · Zbl 0854.68070
[7] Bader, D. A.; Kappes, A.; Meyerhenke, H.; Sanders, P.; Schulz, C.; Wagner, D., Benchmarking for graph clustering and partitioning, Encyclopedia of Social Network Analysis and Mining, 73-82, (2014)
[8] Balas, E.; Ng, S. M., On the set covering polytope: I. all the facets with coefficients in {0, 1, 2}, Mathematical Programming, 43, 57-69, (1989) · Zbl 0674.90079
[9] Barioli, F.; Barrett, W.; Fallat, S.; Hall, H. T.; Hogben, L.; Shader, B., Zero forcing parameters and minimum rank problems, Linear Algebra and its Applications, 433, 2, 401-411, (2010) · Zbl 1209.05139
[10] Barioli, F.; Barrett, W.; Fallat, S. M.; Hall, T.; Hogben, L.; Shader, B., Parameters related to tree-width, zero forcing, and maximum nullity of a graph, Journal of Graph Theory, 72, 2, 146-177, (2013) · Zbl 1259.05112
[11] Benson, K.; Ferrero, D.; Flagg, M.; Furst, V.; Hogben, L.; Vasilevska, V.; Wissman, B., Zero forcing and power domination for graph products, Australasian Journal of Combinatorics, 70, 2, 221, (2018) · Zbl 1383.05225
[12] Ben-Zwi, O.; Hermelin, D.; Lokshtanov, D.; Newman, I., Treewidth governs the complexity of target set selection, Discrete Optimization, 8, 1, 87-96, (2011) · Zbl 1248.90068
[13] Berliner, A., Bozeman, C., Butler, S., Catral, M., Hogben, L., Kroschel, B., Lin, J. C. H., Warnberg, N., & Young, M. (2018). Zero forcing propagation time on oriented graphs. In press.; Berliner, A., Bozeman, C., Butler, S., Catral, M., Hogben, L., Kroschel, B., Lin, J. C. H., Warnberg, N., & Young, M. (2018). Zero forcing propagation time on oriented graphs. In press. · Zbl 1361.05041
[14] Brimkov, B., & Davila, R. (2016). Characterizations of the connected forcing number of a graph. arXiv:1604.00740, 2016.; Brimkov, B., & Davila, R. (2016). Characterizations of the connected forcing number of a graph. arXiv:1604.00740, 2016.
[15] Brimkov, B., Fast, C. C., & Hicks, I. V. (2017a). Graphs with extremal connected forcing numbers. arXiv:1701.08500; Brimkov, B., Fast, C. C., & Hicks, I. V. (2017a). Graphs with extremal connected forcing numbers. arXiv:1701.08500
[16] Brimkov, B.; Hicks, I. V., Complexity and computation of connected zero forcing, Discrete Applied Mathematics, 229, 31-45, (2017) · Zbl 1367.05115
[17] Brimkov, B., Mikesell, D., & Smith, L. (2017b). Connected power domination in graphs. arXiv:1701.08500; Brimkov, B., Mikesell, D., & Smith, L. (2017b). Connected power domination in graphs. arXiv:1701.08500
[18] Buchanan, A.; Sung, J. S.; Butenko, S.; Pasiliao, E. L., An integer programming approach for fault-tolerant connected dominating sets, INFORMS Journal on Computing, 27, 1, 178-188, (2015) · Zbl 1327.90348
[19] Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Physical Review Letters, 99, 10, 100501, (2007)
[20] Burgarth, D.; Giovannetti, V.; Hogben, L.; Severini, S.; Young, M., Logic circuits from zero forcing, Natural Computing, 14, 3, 485-490, (2015)
[21] Butler, S., DeLoss, L., Grout, J., Hall, H. T., LaGrange, J., McKay, T., Smith, J., & Tims, G. (2014). Minimum rank library (Sagehttps://github.com/jasongrout/minimum_rank; Butler, S., DeLoss, L., Grout, J., Hall, H. T., LaGrange, J., McKay, T., Smith, J., & Tims, G. (2014). Minimum rank library (Sagehttps://github.com/jasongrout/minimum_rank
[22] Butler, S.; Grout, J.; Hall, H. T., Using variants of zero forcing to bound the inertia set of a graph, Electronic Journal of Linear Algebra, 30, (2015) · Zbl 1323.05088
[23] Butler, S.; Young, M., Throttling zero forcing propagation speed on graphs, Australasian Journal of Combinatorics, 57, 65-71, (2013) · Zbl 1293.05220
[24] Caro, Y.; West, D. B.; Yuster, R., Connected domination and spanning trees with many leaves, SIAM Journal on Discrete Mathematics, 13, 202-211, (2000) · Zbl 0941.05045
[25] Carvajal, R.; Constantino, M.; Goycoolea, M.; Vielma, J. P.; Weintraub, A., Imposing connectivity constraints in forest planning models, Operations Research, 61, 4, 824-836, (2013) · Zbl 1291.90341
[26] Chiang, C. Y.; Huang, L. H.; Li, B. J.; Wu, J.; Yeh, H. G., Some results on the target set selection problem, Journal of Combinatorial Optimization, 25, 4, 702-715, (2013) · Zbl 1273.90224
[27] Chilakamarri, K. B.; Dean, N.; Kang, C. X.; Yi, E., Iteration index of a zero forcing set in a graph, Bulletin of the Institute of Combinatorics and its Applications, 64, 57-72, (2012) · Zbl 1251.05149
[28] Dantzig, G.; Fulkerson, R.; Johnson, S., Solution of a large-scale traveling-salesman problem, Operations Research, 2, 393-410, (1954)
[29] Desormeaux, W. J.; Haynes, T. W.; Henning, M. A., Bounds on the connected domination number of a graph, Discrete Applied Mathematics, 161, 18, 2925-2931, (2013) · Zbl 1287.05100
[30] Edholm, C.; Hogben, L.; LaGrange, J.; Row, D., Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra and its Applications, 436, 12, 4352-4372, (2012) · Zbl 1241.05076
[31] Ekstrand, J., Positive semidefinite zero forcing, Linear Algebra and its Ap plications, 439, 7, 1862-1874, (2013) · Zbl 1283.05165
[32] Eroh, L., Kang, C., & Yi, E. (2012). Metric dimension and zero forcing number of two families of line graphs. arXiv:1207.6127; Eroh, L., Kang, C., & Yi, E. (2012). Metric dimension and zero forcing number of two families of line graphs. arXiv:1207.6127 · Zbl 1340.05057
[33] Fan, N.; Watson, J. P., Solving the connected dominating set problem and power dominating set problem by integer programming, International Conference on Combinatorial Optimization and Applications, 371-383, (2012), Springer Berlin Heidelberg · Zbl 1358.05214
[34] Fast, C. C., & Hicks, I. V. (2018). Effects of vertex degrees on the zero-forcing number and propagation time of a graph, Discrete Applied Mathematics, in press, 2018, https://doi.org/10.1016/j.dam.2018.05.002; Fast, C. C., & Hicks, I. V. (2018). Effects of vertex degrees on the zero-forcing number and propagation time of a graph, Discrete Applied Mathematics, in press, 2018, https://doi.org/10.1016/j.dam.2018.05.002 · Zbl 1398.05085
[35] Fischetti, M.; Leitner, M.; Ljubić, I.; Luipersbeck, M.; Monaci, M.; Resch, M., Thinning out Steiner trees: A node-based model for uniform edge costs, Mathematical Programming Computation, 1-27, (2016)
[36] Fischetti, M.; Lodi, A., Optimizing over the first Chvátal closure, Mathematical Programming, 110, 3-20, (2007) · Zbl 1192.90125
[37] Fomin, F. V.; Grandoni, F.; Kratsch, D., Solving connected dominating set faster than 2^{n}, Algorithmica, 52, 2, 153-166, (2008) · Zbl 1170.68030
[38] Goldberg, F.; Berman, A., Zero forcing for sign patterns, Linear Algebra and its Applications, 447, 56-67, (2014) · Zbl 1288.05156
[39] Connected Watts-Strogatz small-world graphs (2013). Networkx documentation. Available at: https://networkx.github.io/documentation/networkx-1.8.1/reference/generated/networkx.generators.random_graphs.connected_watts_strogatz_graph.html; Connected Watts-Strogatz small-world graphs (2013). Networkx documentation. Available at: https://networkx.github.io/documentation/networkx-1.8.1/reference/generated/networkx.generators.random_graphs.connected_watts_strogatz_graph.html
[40] Illinois Center for a Smarter Electric Grid (2018). Power flow test cases. Available at http://icseg.iti.illinois.edu/power-cases/; Illinois Center for a Smarter Electric Grid (2018). Power flow test cases. Available at http://icseg.iti.illinois.edu/power-cases/
[41] AIM Special Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra and its Applications, 428, 7, 1628-1648, (2008)
[42] Haynes, T.; Hedetniemi, S.; Hedetniemi, S.; Henning, M., Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics, 15, 4, 519-529, (2002) · Zbl 1006.05043
[43] Hogben, L.; Kingsley, N.; Meyer, S.; Walker, S.; Young, M., Propagation time for zero forcing on a graph, Discrete Applied Mathematics, 160, 13, 1994-2005, (2012) · Zbl 1246.05056
[44] Hogben, L.; Palmowski, K. F.; Roberson, D. E.; Young, M., Fractional zero forcing via three-color forcing games, Discrete Applied Mathematics, 213, 114-129, (2016) · Zbl 1344.05062
[45] Huang, L. H.; Chang, G. J.; Yeh, H. G., On minimum rank and zero forcing sets of a graph, Linear Algebra and its Applications, 432, 2961-2973, (2010) · Zbl 1195.05043
[46] Khajeh, K. G.; Bashar, E.; Rad, A. M.; Gharehpetian, G. B., Integrated model considering effects of zero injection buses and conventional measurements on optimal PMU placement, IEEE Transactions on Smart Grid, 8, 2, 1006-1013, (2017)
[47] Lu, L.; Wu, B.; Tang, Z., Proof of a conjecture on the zero forcing number of a graph, Discrete Applied Mathematics, 213, 223-237, (2016)
[48] Mahaei, S. M.; Hagh, M. T., Minimizing the number of PMUs and their optimal placement in power systems, Electric Power Systems Research, 83, 1, 66-72, (2012)
[49] Meyer, S., Zero forcing sets and bipartite circulants, Linear Algebra and its Applications, 436, 4, 888-900, (2012) · Zbl 1236.05163
[50] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of traveling salesman problems, Journal of the ACM, 7, 326-329, (1960) · Zbl 0100.15101
[51] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization, (1999), Wiley: Wiley New York · Zbl 0944.90001
[52] Quintāo, F. P.; Cunha, A. S.d.; Mateus, G. R.; Lucena, A.; 1305-1314., The k-cardinality tree problem: reformulations and lagrangian relaxation, Discrete Applied Mathematics, 158, 12, 1305-1314, (2010) · Zbl 1231.05139
[53] Row, D. D., A technique for computing the zero forcing number of a graph with a cut-vertex, Linear Algebra and its Applications, 436, 4423-4432, (2012) · Zbl 1241.05086
[54] Trefois, M.; Delvenne, J. C., Zero forcing number, constrained matchings and strong structural controllability, Linear Algebra and its Applications, 484, 199-218, (2015) · Zbl 1325.05057
[55] Wang, Y.; Buchanan, A.; Butenko, S., On imposing connectivity constraints in integer programs, Mathematical Programming, 166, 1-31, (2017) · Zbl 1386.90023
[56] Warnberg, N., Positive semidefinite propagation time, Discrete Applied Mathematics, 198, 274-290, (2016) · Zbl 1327.05128
[57] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[58] West, D. B., Introduction to graph theory, (2001), Prentice Hall, Inc.: Prentice Hall, Inc. Upper Saddle River, NJ
[59] Yang, B., Fast-mixed searching and related problems on graphs, Theoretical Computer Science, 507, 100-113, (2013) · Zbl 1302.05197
[60] Zhao, M.; Kang, L.; Chang, G., Power domination in graphs, Discrete Mathematics, 306, 15, 1812-1816, (2006) · Zbl 1099.05065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.