4
$\begingroup$

I am currently working on the isomorphism of graphs, hyper-graphs. The graph isomorphism of graphs of degree at most three (trivalent) known to be in $P$. E.M Luks has given an algorithm for trivalent graph isomorphism, which is algebraic in nature.

Question : Is there a known graph isomorphism algorithm for graphs of degree at most three other than E.M Luks algorithm? Is there exist a combinatorial algorithm for trivalent graph isomorphism?

I thought of using Weisfeiler-Lehman procedure, but it fails on regular graphs.

Edit : I will use $k$-Weisfeiler-Lehman procedure; it is going to fail on the very small class of graphs called iso-regular graphs, Now I will divide this class into two classes;bounded tree width and unbounded tree width. For bounded tree width we already have a polynomial time (FPT algorithm) algorithm, unbounded tree-width class can be further divided into two subclasses; planar and non-planar, for planar, we already have a combinatorial algorithm that runs in $O(n^2)$ time, Now we are left with non-planar unbounded tree width iso-regular graphs. One thing is that I am not able to come up with an example of a graph, which is a non-planar unbounded tree width iso-regular graph of degree at most three.

$k$-iso-rgular graphs or $k$-tuple regular graphs : Graphs in which the number of common neighbours of any k-tuple of a given isomorphism type is constant (for instance, strongly regular graphs are 2-isoregular).

$\endgroup$
  • $\begingroup$ If you're going to try to avoid bounded tree-width, you might also try avoiding other FPT algorithms: bounded clique-width, bounded genus (or more generally bounded topological Hadwiger number), bounded eigenvalue multiplicity; see, e.g. Marx-Pilipczuk. Finding degree 3 graphs w/ all of these parameters unbounded could be hard; on the other hand, maybe having so many constraints will point you towards a construction... $\endgroup$ – Joshua Grochow Sep 12 '17 at 16:21
  • 1
    $\begingroup$ Also, the thing to really try is WL together with individualizing a small number of vertices. $\endgroup$ – Joshua Grochow Sep 12 '17 at 17:10
  • $\begingroup$ I think it is possible to come-up with an $O(\sqrt n \log n)$ individualisation set size, see this people.cs.uchicago.edu/~laci/papers/13focs-SRG.pdf, but smaller size seems difficult. $\endgroup$ – new Sep 20 '17 at 12:34
5
$\begingroup$

Even higher-dimensional WL is known not to work in poly time on graphs of degree 4 (Cai-Furer-Immerman). I do not know if higher-dimensional WL might work on graphs of degree 3, but I also don't know of a result ruling this out either. Aside from Babai's general algorithm (which is quasi-polynomial, not polynomial), I do not know another algorithm for degree 3 other than the one you mention.

$\endgroup$
  • $\begingroup$ How about degree $\leq 3$ and bipartite? $\endgroup$ – Turbo Sep 10 '17 at 1:39
  • $\begingroup$ @777: that's equivalent to general degree $\leq 3$, up to a quadratic term. Just add a new vertex on every edge. $\endgroup$ – Joshua Grochow Sep 10 '17 at 18:51
  • $\begingroup$ $k$-WL fails on iso-regular graphs, where $k$ is constant and there are at most degree three iso-regular graphs. $\endgroup$ – new Sep 11 '17 at 8:12
  • $\begingroup$ @shivd what does "iso-regular" mean? $\endgroup$ – Joshua Grochow Sep 12 '17 at 2:17
  • 1
    $\begingroup$ @Joshua Grochow See page no -5, second paragraph in the link arxiv.org/pdf/1101.5211.pdf $\endgroup$ – new Sep 12 '17 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.