RECORD
Sherali-Adams Relaxations of Graph Isomorphism Polytopes
Combinatorics · Submitted 4 Jul 2011
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope needs Omega(n) iterations in the worst case before converging to the convex hull of integer points.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali-Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope needs Omega(n) iterations in the worst case before converging to the convex hull of integer points. We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler-Lehman algorithm, which we show can also be characterized in terms of the Sherali-Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. | contribution 0.94 | 0.86 | 0.08 | asserted 0.89 |
| s1 | In particular, the Sherali-Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. | result 0.53 | 0.90 | 0.34 | asserted 1.00 |
| s2 | This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. | contribution 0.48 | 0.46 | 0.10 | asserted 1.00 |
| s3 | We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope needs Omega(n) iterations in the worst case before converging to the convex hull of integer points. | result 1.00 | 0.94 | 0.47 | asserted 1.00 |
| s4 | We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler-Lehman algorithm, which we show can also be characterized in terms of the Sherali-Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms. | result 0.71 | 0.88 | 0.16 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali-Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope needs Omega(n) iterations in the worst case before converging to the convex hull of integer points. We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler-Lehman algorithm, which we show can also be characterized in terms of the Sherali-Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms.
Human review
How the literature uses it
2 arXiv papers cite this in 4 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 2 papers
-
Recently, generic mathematical programming and algebraic techniques applied to graph isomorphism have received considerable attention [ref] .
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism · Introduction · 0.99
-
O'Donnell, Wright, Wu, and Zhou [ref] and Codenotti, Schoenbeck, and Snook [ref] studied the Lasserre hierarchy [ref] of semi-definite relaxations of the integer linear program for GI.
Limitations of Algebraic Approaches to Graph Isomorphism Testing · Introduction · 0.93
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.