Lower bounds for positive semidefinite zero forcing and their applications

详细信息    查看全文

• 作者：Boting Yang
• 关键词：Zero forcing number ; Minimum rank ; Tree cover number ; Positive semidefinite zero forcing number ; Maximum positive semidefinite nullity
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：81-105
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.