Skip to main content
corrected reference
Source Link
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

One should distinguish between practical graph isomorphism and theoretical worst-case complexity. As Mikhail Tikhomirov mentioned, Babai's recent theoretical breakthrough gives the best asymptotic worst-case complexity, but his paper does not yield any breakthrough in practical graph isomorphism.

Practically, regular graphs are the hardest but for the rather uninteresting reason that if you have a pair of non-regular graphs then you can partition the vertices according to degree, and this generally breaks down the problem into easier sub-problems—the bottleneck is usually determining isomorphism of the "regular parts" and not figuring out whether they're pieced together isomorphically.

Variants of Brendan McKay's "nauty" algorithm are still the ones that are used in practice unless you know that you're dealing with a special class of graphs whose structure you can exploit. Perhaps surprisingly, it is not always the "most symmetric" graphs that are the hardest. One good reference is Deo and TenerTener's Ph.D. thesis. It is possible to construct hard instances for nauty, but some of these hard instances are relatively easily distinguishable by a special-purpose algorithm that actually requires a lot of symmetry. So, if we broaden the original question to ask if "highly symmetric" graphs are the hardest for the standard practical graph isomorphism algorithms, and if there are special algorithms that can handle these "hard cases," then there is a sense in which the answer is yes. However, this probably should be interpreted as saying that we still don't fully understand what the "hardest cases" of graph isomorphism are.

One should distinguish between practical graph isomorphism and theoretical worst-case complexity. As Mikhail Tikhomirov mentioned, Babai's recent theoretical breakthrough gives the best asymptotic worst-case complexity, but his paper does not yield any breakthrough in practical graph isomorphism.

Practically, regular graphs are the hardest but for the rather uninteresting reason that if you have a pair of non-regular graphs then you can partition the vertices according to degree, and this generally breaks down the problem into easier sub-problems—the bottleneck is usually determining isomorphism of the "regular parts" and not figuring out whether they're pieced together isomorphically.

Variants of Brendan McKay's "nauty" algorithm are still the ones that are used in practice unless you know that you're dealing with a special class of graphs whose structure you can exploit. Perhaps surprisingly, it is not always the "most symmetric" graphs that are the hardest. One good reference is Deo and Tener. It is possible to construct hard instances for nauty, but some of these hard instances are relatively easily distinguishable by a special-purpose algorithm that actually requires a lot of symmetry. So, if we broaden the original question to ask if "highly symmetric" graphs are the hardest for the standard practical graph isomorphism algorithms, and if there are special algorithms that can handle these "hard cases," then there is a sense in which the answer is yes. However, this probably should be interpreted as saying that we still don't fully understand what the "hardest cases" of graph isomorphism are.

One should distinguish between practical graph isomorphism and theoretical worst-case complexity. As Mikhail Tikhomirov mentioned, Babai's recent theoretical breakthrough gives the best asymptotic worst-case complexity, but his paper does not yield any breakthrough in practical graph isomorphism.

Practically, regular graphs are the hardest but for the rather uninteresting reason that if you have a pair of non-regular graphs then you can partition the vertices according to degree, and this generally breaks down the problem into easier sub-problems—the bottleneck is usually determining isomorphism of the "regular parts" and not figuring out whether they're pieced together isomorphically.

Variants of Brendan McKay's "nauty" algorithm are still the ones that are used in practice unless you know that you're dealing with a special class of graphs whose structure you can exploit. Perhaps surprisingly, it is not always the "most symmetric" graphs that are the hardest. One good reference is Tener's Ph.D. thesis. It is possible to construct hard instances for nauty, but some of these hard instances are relatively easily distinguishable by a special-purpose algorithm that actually requires a lot of symmetry. So, if we broaden the original question to ask if "highly symmetric" graphs are the hardest for the standard practical graph isomorphism algorithms, and if there are special algorithms that can handle these "hard cases," then there is a sense in which the answer is yes. However, this probably should be interpreted as saying that we still don't fully understand what the "hardest cases" of graph isomorphism are.

Source Link
Timothy Chow
  • 82.7k
  • 26
  • 363
  • 587

One should distinguish between practical graph isomorphism and theoretical worst-case complexity. As Mikhail Tikhomirov mentioned, Babai's recent theoretical breakthrough gives the best asymptotic worst-case complexity, but his paper does not yield any breakthrough in practical graph isomorphism.

Practically, regular graphs are the hardest but for the rather uninteresting reason that if you have a pair of non-regular graphs then you can partition the vertices according to degree, and this generally breaks down the problem into easier sub-problems—the bottleneck is usually determining isomorphism of the "regular parts" and not figuring out whether they're pieced together isomorphically.

Variants of Brendan McKay's "nauty" algorithm are still the ones that are used in practice unless you know that you're dealing with a special class of graphs whose structure you can exploit. Perhaps surprisingly, it is not always the "most symmetric" graphs that are the hardest. One good reference is Deo and Tener. It is possible to construct hard instances for nauty, but some of these hard instances are relatively easily distinguishable by a special-purpose algorithm that actually requires a lot of symmetry. So, if we broaden the original question to ask if "highly symmetric" graphs are the hardest for the standard practical graph isomorphism algorithms, and if there are special algorithms that can handle these "hard cases," then there is a sense in which the answer is yes. However, this probably should be interpreted as saying that we still don't fully understand what the "hardest cases" of graph isomorphism are.