Sherali-Adams relaxations and indistinguishability in counting logics
Sherali-Adams relaxations and indistinguishability in counting logics
复制标题
计数逻辑中的 Sherali-Adams 松弛和不可区分性
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Elitza N. Maneva
中科院分区：
文献类型：
--
作者：
Albert Atserias;Elitza N. Maneva
具有邻接矩阵A和B的两个图是同构的，如果存在置换矩阵P，且单位元PTAP = B成立。通过乘以P并将置换矩阵松弛为双随机矩阵，导致称为分数同构的线性规划松弛。我们表明，层次的Sherali-Adams（SA）层次的线性规划松弛适用于分数同构交错的权力与一个著名的颜色细化启发式图同构称为Weisfeiler-Lehman算法的水平，或等价地，与水平的不确定性的逻辑计数量词和有限数量的变量。这种紧密的联系产生了相当惊人的后果。例如，从Grohe在具有计数量词的逻辑的上下文中的一个深入结果可以立即得出，SA的固定数量的水平足以确定平面图和无子图的同构。我们也提供有限模型理论和多面体组合学的应用。首先，我们证明了某些性质的图，如具有一个规定的值的流循环，是可定义的无穷逻辑计数与有限数量的变量。其次，我们利用了一个下界结构，由于蔡，Fürer和Immerman在计数逻辑的背景下，给出简单的显式的例子，表明顶点覆盖和切割多面体的SA松弛不达到其整数壳为Ω（n）水平，其中n是在图中的顶点数。
Two graphs with adjacency matrices A and B are isomorphic if there exists a permutation matrix P for which the identity PTAP = B holds. Multiplying through by P and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali-Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler-Lehman algorithm, or equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers, that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications both in finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow-circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to Ω(n) levels, where n is the number of vertices in the graph.