An integer program for positive semidefinite zero forcing in graphs
An integer program for positive semidefinite zero forcing in graphs
复制标题
DOI：
10.1002/net.21947
复制
发表时间：
2020-05
期刊：
影响因子：
2.1
通讯作者：
Logan A. Smith;Derek Mikesell;Illya V. Hicks
中科院分区：
文献类型：
--
作者：
Logan A. Smith;Derek Mikesell;Illya V. Hicks
半正定迫零是一个动态的图形处理过程，其中一个初始的顶点子集被着色，并可能导致其他顶点通过一组颜色变化规则被着色。使所有其他顶点着色的子集称为PSD迫零集;图的PSD迫零数是其PSD迫零集所达到的最小基数。PSD迫零数特别令人感兴趣，因为它限制了线性代数中流行的最小秩和PSD最小秩问题的解决方案。本文引入PSD迫零集的分块集，并利用分块集构造了计算一般图的PSD迫零数的第一个整数规划。结果表明，该IP的线性松弛的可行域的方面对应于迫零的连通子图，但确定最小基数连通子图一般是NP-困难的。辅助IP用于找到这些阻塞集也给出了，使主IP通过约束生成来解决。实验比较所提出的方法和现有的算法，证明提高了运行时的性能，特别是在密集和稀疏的图形。
Positive semidefinite (PSD) zero forcing is a dynamic graph process in which an initial subset of vertices are colored and may cause additional vertices to become colored through a set of color changing rules. Subsets which cause all other vertices to become colored are called PSD zero forcing sets; the PSD zero forcing number of a graph is the minimum cardinality attained by its PSD zero forcing sets. The PSD zero forcing number is of particular interest as it bounds solutions for the minimum rank and PSD min rank problems, both popular in linear algebra. This paper introduces blocking sets for PSD zero forcing sets which are used to formulate the first integer program (IP) for computing PSD zero forcing numbers of general graphs. It is shown that facets of the feasible region of this IP's linear relaxation correspond to zero forcing forts which induce connected subgraphs, but that identifying min cardinality connected forts is NP ‐hard in general. Auxiliary IPs used to find these blocking sets are also given, enabling the master IP to be solved via constraint generation. Experiments comparing the proposed methods and existing algorithms are provided demonstrating improved runtime performance, particularly so in dense and sparse graphs.