|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Graph Isomorphism, Color Refinement, and Compactness | | V. Arvind
; Johannes Köbler
; Gaurav Rattan
; Oleg Verbitsky
; | | Date: |
4 Feb 2015 | | Abstract: | Color refinement is a classical technique to show that two given graphs $G$
and $H$ are non-isomorphic; it is very efficient, even if incomplete in
general. We call a graph $G$ amenable to color refinement if this algorithm
succeeds in distinguishing $G$ from any non-isomorphic graph $H$. Babai,
ErdH{o}s, and Selkow (1982) proved that almost all graphs $G$ are amenable. We
here determine the exact range of applicability of color refinement by showing
that the class of all amenable graphs is recognizable in time $O((n+m)log n)$,
where $n$ and $m$ denote the number of vertices and the number of edges in the
input graph.
Furthermore, we prove that amenable graphs are compact in the sense of
Tinhofer (1991), that is, their polytopes of fractional automorphisms are
integral. The concept of compactness was introduced in order to identify the
class of graphs $G$ for which isomorphism $Gcong H$ can be decided by
computing an extreme point of the polytope of fractional isomorphisms from $G$
to $H$ and checking if this point is integral. Our result implies that this
linear programming approach to isomorphism testing has the applicability range
at least as large as the combinatorial approach based on color refinement. | | Source: | arXiv, 1502.1255 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER