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).

Improve this question
$\endgroup$
3
  • $\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
    Commented Sep 12, 2017 at 16:21
  • 1
    $\begingroup$ Also, the thing to really try is WL together with individualizing a small number of vertices. $\endgroup$
    – Joshua Grochow
    Commented Sep 12, 2017 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
    Commented Sep 20, 2017 at 12:34

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ How about degree $\leq 3$ and bipartite? $\endgroup$
    – Turbo
    Commented Sep 10, 2017 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
    Commented Sep 10, 2017 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
    Commented Sep 11, 2017 at 8:12
  • $\begingroup$ @shivd what does "iso-regular" mean? $\endgroup$
    – Joshua Grochow
    Commented Sep 12, 2017 at 2:17
  • 1
    $\begingroup$ @Joshua Grochow See page no -5, second paragraph in the link arxiv.org/pdf/1101.5211.pdf $\endgroup$
    – new
    Commented Sep 12, 2017 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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