Amb motiu del tancament d'estiu, la validació de documents es reprendrà a partir del 28 d'agost de 2026. Disculpeu les molèsties.
Con motivo del cierre de verano, la validación de documentos se reanudará a partir del 28 de agosto de 2026. Disculpad las molestias
Due to the summer closure, document validation will resume starting August 28, 2026. We apologize for any inconvenience.

Fitxers

619363.pdf (339 KB)

Tipus de document

Article

Versió

Versió publicada

Data de publicació

2013-01-17

Tots els drets reservats

Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/33855

Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Títol de la revista

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

http://dx.doi.org/10.1137/120867834

Resum

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.

Matèries

Lògica de primer ordre, Programació lineal, Teoria de grafs

Matèries (anglès)

First-order logic, Linear programming, Graph theory

Citació

Col·leccions

Articles publicats en revistes (Matemàtiques i Informàtica)

Citació

ATSERIAS, Albert and MANEVA, Elitza. Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM Journal on Computing. 2013. Vol. 42, num. 1, pags. 112-137. ISSN 0097-5397. [consulted: 11 of August of 2026]. Available at: https://hdl.handle.net/2445/33855

Exportar metadades

JSON - METS

Compartir registre