Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Grohe, Martin; Otto, Martin http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-36790
URL:

;

Pebble Games and Linear Equations

pdf-format:


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 =		{http://dx.doi.org/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
Seminar: Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL
Issue date: 2012
Date of publication: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI