Pebble Games and Linear Equations

Details Pebble Games and Linear Equations Pebble Games and Linear Equations

2012-04-09

arxiv.org/abs/1204.1990v1

Computer Science

Logic in Computer Science

Scientific paper

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 (1994), is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva (2012), 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.

Affiliated with

Also associated with

No associations

Rating

Pebble Games and Linear Equations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pebble Games and Linear Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pebble Games and Linear Equations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643698