License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2012.289
URN: urn:nbn:de:0030-drops-36790
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3679/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin ; Otto, Martin

Pebble Games and Linear Equations

pdf-format:
25.pdf (0.5 MB)

Abstract

We give a new, simplified and detailed account of the correspondence
between levels of the Sherali-Adams relaxation of graph isomorphism
and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler-Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Ramana, Scheinerman and Ullman, is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva, who prove that the two resulting hierarchies interleave.

In carrying this analysis further, we here give (a) a precise characterisation of the level-k Sherali-Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali-Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict.

We also investigate the variation based on boolean arithmetic instead
of real/rational arithmetic and obtain analogous correspondences and
separations for plain k-pebble equivalence (without counting). Our
results are driven by considerably simplified accounts of the
underlying combinatorics and linear algebra.

BibTeX - Entry

@InProceedings{grohe_et_al:LIPIcs:2012:3679,
  author =	{Martin Grohe and Martin Otto},
  title =	{{Pebble Games and Linear Equations}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{289--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{Patrick C{\'e}gielski and Arnaud Durand},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3679},
  URN =		{urn:nbn:de:0030-drops-36790},
  doi =		{10.4230/LIPIcs.CSL.2012.289},
  annote =	{Keywords: Finite model theory, finite variable logics, graph isomorphism, Weisfeiler- Lehman algorithm, linear programming, Sherali–Adams hierarchy}
}

Keywords: Finite model theory, finite variable logics, graph isomorphism, Weisfeiler- Lehman algorithm, linear programming, Sherali–Adams hierarchy
Collection: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue Date: 2012
Date of publication: 03.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI