Abstract
The positive zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring, and is related to a more conventional version of zero forcing. We establish a relation between the zero forcing and the fast-mixed searching, which implies some NP-completeness results for the zero forcing problem. For chordal graphs much is understood regarding the relationships between positive zero forcing and clique coverings. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive zero forcing number of chordal graphs. We also prove that it is NP-complete to determine if a graph has a positive zero forcing set with an additional property.
Shaun Fallat: Research supported in part by an NSERC Discovery Research Grant, Application No.: RGPIN-2014-06036.
Karen Meagher: Research supported in part by an NSERC Discovery Research Grant, Application No.: RGPIN-341214-2013.
Boting Yang: Research supported in part by an NSERC Discovery Research Grant, Application No.: RGPIN-2013-261290.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
AIM Minimum Rank-Special Graphs Work Group: Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428(7), 1628–1648 (2008)
Barioli, F., Barrett, W., Fallat, S., Hall, H.T., Hogben, L., Shader, B., van den Driessche, P., van der Holst, H.: Parameters related to tree-width, zero forcing, and maximum nullity of a graph. J. Graph Theory 72, 146–177 (2013)
Barioli, F., Barrett, W., Fallat, S., Hall, H.T., Hogben, L., Shader, B., van den Driessche, P., van der Holst, H.: Zero forcing parameters and minimum rank problems. Linear Algebra Appl. 433(2), 401–411 (2010)
Bienstock, D., Seymour, P.: Monotonicity in graph searching. J. Algorithms 12, 239–245 (1991)
Booth, M., Hackney, P., Harris, B., Johnson, C.R., Lay, M., Mitchell, L.H., Narayan, S.K., Pascoe, A., Steinmetz, K., Sutton, B.D., Wang, W.: On the minimum rank among positive semidefinite matrices with a given graph. SIAM J. Matrix Anal. Appl. 30, 731–740 (2008)
Burgarth, D., Giovannetti, V.: Full control by locally induced relaxation. Phys. Rev. Lett. 99(10), 100501 (2007)
Dyer, D., Yang, B., Yaşar, Ö.: On the fast searching problem. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol. 5034, pp. 143–154. Springer, Heidelberg (2008)
Ekstrand, J., Erickson, C., Hall, H.T., Hay, D., Hogben, L., Johnson, R., Kingsley, N., Osborne, S., Peters, T., Roat, J., et al.: Positive semidefinite zero forcing. Linear Algebra Appl. 439, 1862–1874 (2013)
Ekstrand, J., Erickson, C., Hay, D., Hogben, L., Roat, J.: Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial \(2\)-trees. Electron. J. Linear Algebra 23, 79–97 (2012)
Kirousis, L., Papadimitriou, C.: Searching and pebbling. Theoret. Comput. Sci. 47, 205–218 (1986)
Megiddo, N., Hakimi, S., Garey, M., Johnson, D., Papadimitriou, C.: The complexity of searching a graph. J. ACM 35, 18–44 (1988)
Scheinerman, E.R., Trenk, A.N.: On the fractional intersection number of a graph. Graphs Combin. 15, 341–351 (1999)
Yang, B.: Fast-mixed searching and related problems on graphs. Theoret. Comput. Sci. 507(7), 100–113 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fallat, S., Meagher, K., Yang, B. (2014). The Complexity of the Positive Semidefinite Zero Forcing. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_51
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_51
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)