Please use this identifier to cite or link to this item:
http://hdl.handle.net/2445/33855
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Atserias, Albert | - |
dc.contributor.author | Maneva, Elitza | - |
dc.date.accessioned | 2013-02-19T11:54:16Z | - |
dc.date.available | 2013-02-19T11:54:16Z | - |
dc.date.issued | 2013-01-17 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/2445/33855 | - |
dc.description.abstract | Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{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 in both 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 $\Omega(n)$ levels, where $n$ is the number of vertices in the graph. | - |
dc.format.extent | 26 p. | - |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics | - |
dc.relation.isformatof | Reproducció del document publicat a: http://dx.doi.org/10.1137/120867834 | - |
dc.relation.ispartof | SIAM Journal on Computing, 2013, vol. 42, num. 1, p. 112-137 | - |
dc.relation.uri | http://dx.doi.org/10.1137/120867834 | - |
dc.rights | (c) Society for Industrial and Applied Mathematics., 2013 | - |
dc.source | Articles publicats en revistes (Matemàtiques i Informàtica) | - |
dc.subject.classification | Lògica de primer ordre | - |
dc.subject.classification | Programació lineal | - |
dc.subject.classification | Teoria de grafs | - |
dc.subject.other | First-order logic | - |
dc.subject.other | Linear programming | - |
dc.subject.other | Graph theory | - |
dc.title | Sherali-Adams Relaxations and Indistinguishability in Counting Logics | eng |
dc.type | info:eu-repo/semantics/article | - |
dc.type | info:eu-repo/semantics/publishedVersion | - |
dc.identifier.idgrec | 619363 | - |
dc.date.updated | 2013-02-19T11:42:38Z | - |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | - |
Appears in Collections: | Articles publicats en revistes (Matemàtiques i Informàtica) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
619363.pdf | 339 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.