Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T00:26:04.187Z Has data issue: false hasContentIssue false
  • English
  • Français

PEBBLE GAMES AND LINEAR EQUATIONS

Published online by Cambridge University Press:  22 July 2015

MARTIN GROHE  and
MARTIN OTTO
MARTIN GROHE
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE RWTH AACHEN UNIVERSITYGERMANYE-mail: [email protected]
MARTIN OTTO
Affiliation:
DEPARTMENT OF MATHEMATICS TECHNISCHE UNIVERSITÄT DARMSTADTGERMANYE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], 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.

Keywords

Graph isomorphismSherali-Adams hierarchyfinite variable logics
Type
Articles
Information
The Journal of Symbolic Logic , Volume 80 , Issue 3 , September 2015 , pp. 797 - 844
Copyright
Copyright © The Association for Symbolic Logic 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Atserias, A. and Maneva, E., Sherali–Adams relaxations and indistinguishability in counting logics, Innovations in Theoretical Computer Science (ITCS), 2012.CrossRefGoogle Scholar
Barwise, J., On Moschovakis closure ordinals, this Journal, vol. 42 (1977), pp. 292–296.Google Scholar
Berkholz, C. and Grohe, M., Limitations of algebraic approaches to graph isomorphism testing, ArXiv, vol. arXiv:1502.05912 [cs.CC] (2015).Google Scholar
Bienstock, D. and Ozbay, N., Tree-width and the Sherali-Adams operator. Discrete Optimization, vol. 1 (2004), pp. 13–21.CrossRefGoogle Scholar
Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., and Pitassi, T., Rank bounds and integrality gaps for cutting planes procedures, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 318–327.Google Scholar
Cai, J., Fürer, M., and Immerman, N., An optimal lower bound on the number of variables for graph identification. Combinatorica, vol. 12 (1992), pp. 389–410.CrossRefGoogle Scholar
Charikar, M., Makarychev, K., and Makarychev, Y., Integrality gaps for Sherali-Adams relaxations, Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 283–292.Google Scholar
Grädel, E. and Otto, M., Inductive definability with counting on finite structures, Computer Science Logic, CSL ‘92(Börger, E., Jäger, G., Kleine Büning, H., Martini, S., and Richter, M.M., editors), Lecture Notes in Computer Science, vol. 702, Springer-Verlag, 1993, pp. 231–247.CrossRefGoogle Scholar
Grohe, M., Fixed-point definability and polynomial time on graphs with excluded minors, Proceedings of the 25th IEEE Symposium on Logic in Computer Science, 2010.Google Scholar
Hella, L., Logical hierarchies in PTIME, Proceedings of the 6th IEEE Symposium on Logic in Computer Science, 1992, pp. 360–368.Google Scholar
Immerman, N., Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
Immerman, N. and Lander, E., Describing graphs: A first-order approach to graph canonization, Complexity theory retrospective (Selman, A., editor), Springer-Verlag, 1990, pp. 59–81.CrossRefGoogle Scholar
Laubner, B., Capturing polynomial time on interval graphs, Proceedings of the 25th IEEE Symposium on Logic in Computer Science, 2010, pp. 199–208.Google Scholar
Malkin, P.N., Sherali–Adams relaxations of graph isomorphism polytopes. Discrete Optimization, vol.12 (2014), pp. 73–97.CrossRefGoogle Scholar
Mathieu, C. and Sinclair, A., Sherali-Adams relaxations of the matching polytope, Proceedings of the 41st ACM Symposium on Theory of Computing, 2009, pp. 293–302.Google Scholar
Otto, M., Bounded variable logics and counting – A study in finite models, Lecture Notes in Logic, vol. 9, Springer-Verlag, 1997.CrossRefGoogle Scholar
Ramana, M., Scheinerman, E., and Ullman, D., Fractional isomorphism of graphs. Discrete Mathematics, vol. 132 (1994), pp. 247–265.CrossRefGoogle Scholar
Scheinerman, E. and Ullman, D., Fractional graph theory, Wiley, 1997.Google Scholar
Schoenebeck, G., Linear level Lasserre lower bounds for certain k-CSPs, Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 593–602.Google Scholar
Schoenebeck, G., Trevisan, L., and Tulsiani, M., Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut, Proceedings of the 39th ACM Symposium on Theory of Computing, 2007, pp. 302–310.Google Scholar
Sherali, H.D. and Adams, W.P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics, vol. 3 (1990), p. 411.CrossRefGoogle Scholar
Tinhofer, G., Graph isomorphism and theorems of Birkhoff type. Computing, vol. 36 (1986), pp. 285–300.CrossRefGoogle Scholar
Tinhofer, G., A note on compact graphs. Discrete Applied Mathematics, vol. 30 (1991), pp. 253–264.CrossRefGoogle Scholar
Weisfeiler, B., On construction and identification of graphs, Lecture Notes in Mathematics, vol. 558, Springer-Verlag, 1976.CrossRefGoogle Scholar