1
$\begingroup$

Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$

All weights on the graph edges are from this set.

$\endgroup$
  • 4
    $\begingroup$ Could you define exactly what the problem is when there are weights on the edges? What is an isomorphism in this context? Why do you think that adding weights makes the problem easier? Isn't the unweighted graph isomorphism problem just the special case where every edge has unit weight? $\endgroup$ – David Richerby Feb 28 '16 at 8:43
  • $\begingroup$ The fact that there are different weights doesn't mean that they ever get used... Even if they do get used, they don't really make the problem any easier. See my comment to my answer. $\endgroup$ – Yuval Filmus Feb 28 '16 at 19:17
  • 1
    $\begingroup$ Are you looking for an algorithm that works always or with high probability? If so, probability over what? The choice of weights? $\endgroup$ – Yuval Filmus Feb 28 '16 at 19:33
  • $\begingroup$ @YuvalFilmus For every $n$ fix a set of weights. For every input graphs you assign weights uniformly from a distribution. Then you feed in the input graph, weights and the second graph to the black box and the black box returns you the second graph. Then you have to decide iso on these two graphs. So the probability is over all assignments of weights (the weight set is fixed for every $n$ in some worst case way). If this has an algorithm that is in $\mathsf{BPP}$ then in theory it should be conjecturally derandomizable. $\endgroup$ – user39969 Feb 28 '16 at 20:23
  • 1
    $\begingroup$ It seems that the question has changed since after you got some good answers. Changing a question in a way that invalidates existing answers is frowned upon. If you want to ask about the randomized version of this problem, I suggest you post a new question (and edit this question to match the answers below). $\endgroup$ – D.W. Feb 29 '16 at 7:29
6
$\begingroup$

This on contrary appears to be a problem of greater difficulty than graph isomorphism. If you had a polynomial time solution to this problem,you can reduce graph isomorphism to it by keeping each edge weight say equal to some constant $c$. Also graph isomorphism is not known to have a polynomial time solution. It is a still an open question.

$\endgroup$
  • $\begingroup$ I am thinking of a scenario of where number of weights depend on $n$. $\endgroup$ – user39969 Feb 28 '16 at 18:35
5
$\begingroup$

As sasha mentions, your problem is actually a generalization of the usual graph isomorphism. To put it differently, graph isomorphism is a special case of your problem, in which all weights are the same. Therefore your problem can only be more difficult.

On the other hand, it is easy to reduce your problem to the usual graph isomorphism. Assuming that only edges have weights, the idea is to split each edge into a path of length two, and to attach to the middle node a clique whose size depends on the weight (we only need that different weights have different clique sizes, and that the cliques be large enough). So your problem is GI-complete, i.e., equivalent to graph isomorphism.

$\endgroup$
  • $\begingroup$ " Therefore your problem can only be more difficult." Well, not strictly true. I mean: ILP is a special case of LP, yet LP is in P while ILP is NP-complete. $\endgroup$ – Bakuriu Feb 28 '16 at 14:28
  • 5
    $\begingroup$ No, ILP is not a special case of LP. You can't model an arbitrary ILP as an LP. $\endgroup$ – Yuval Filmus Feb 28 '16 at 15:20
  • $\begingroup$ I am thinking of a scenario of where number of weights depend on $n$, this should be easier i think. $\endgroup$ – user39969 Feb 28 '16 at 18:47
  • $\begingroup$ This won't help. Given an instance of GI, you can add a disconnected part with as many weights as you want to both graphs. This way you can even have $n-n^\alpha$ different weights appearing in the graphs. $\endgroup$ – Yuval Filmus Feb 28 '16 at 19:16
  • $\begingroup$ @YuvalFilmus I see the issue may be I am not communicating well and I have now updated. $\endgroup$ – user39969 Feb 28 '16 at 19:20
3
$\begingroup$

As others pointed out already, graph isomorphism is a special case of weighted graph isomorphism, where all edges have the same weight. And on the other hand, weighted graph isomorphism can be reduced to graph isomorphism.

In fact, most isomorphism problems for finite structures turn out to be essentially equivalent to graph isomorphism. A theoretical construction showing this which tries to keep the valence of the resulting graphs as small as possible is given in Graph Isomorphism, General Remarks by Gary L. Miller. The presentation Practical Graph Isomorphism, II by Brendan McKay and Adolfo Piperno uses a more practical approach to convey the same message. They first highlight the Ubiquity of graph isomorphism with concrete examples, and then mention Permutation equivalence of linear codes, which is a rare example of a finite structure whose isomorphism problem is not known to be reducible to graph isomorphism. Very efficient practical reductions of the mentioned examples to the (vertex) colored (di)graph isomorphism problem solved by nauty and Traces can be found in section "14 Variations" of the nauty and Traces User’s Guide (Version 2.5):

If the original graph has $n$ vertices and $k$ colours, the new graph has $O(n \log k)$ vertices. This can be improved to $O(n \sqrt{\log k})$ vertices by also using edges that are not horizontal, but this needs care.

$\endgroup$
  • $\begingroup$ Would you mind be more specific about how to reduce weighted graph isomorphism to unweighted isomorphism? $\endgroup$ – apen May 31 at 0:53
2
$\begingroup$

The problem is in fact easier than graph isomorphism for a directed graph when the weights are all distinct. I wonder if this was the original intent of the question.

For distinct-weighted directed graphs A and B with same number of vertices $n$ and edges $e$, do the following:

  • Sort the edge weights of A and B in decreasing order.
  • Maintain a labeling $\theta$ of vertices of graph B, initialized to the empty set $\phi$. We will fill this labeling in our algorithm and check if we get any contradictory labels. Let us call the label of a vertex $u$ under the labelling $\theta$, $\theta(u)$
  • iterate over edges $e_i=(u_i, v_i)$ in A and corresponding edge $e_i' = (u_i', v_i')$ in B in the sorted order
    • if $weight(e_i) \neq weight(e_i')$ then graphs are not isomorphic. Terminate
    • if $\theta(u_i') == \phi$, then $\theta := \theta\ \cup (u_i', u_i)$
    • if $\theta(v_i') == \phi$, then $\theta := \theta\ \cup (v_i', v_i)$
    • if $\theta(u_i') \neq \phi$ and $\theta(u_i') \neq u_i$ then graphs are not isomorphic. Terminate
    • if $\theta(v_i') \neq \phi$ and $\theta(v_i') \neq v_i$ then graphs are not isomorphic. Terminate
  • if not terminated yet, then graphs are isomorphic. Terminate and enjoy a cup of tea :-)

The running time is $O(e.log(e))$ for sorting edges and $e$ for the single pass over the edges.

The problem is not as useless as it sounds. For example, directed, distinct edge-weighted graph isomorphism can be used to find out if two given Bayesian Networks are isomorphic or not. This can be used to transfer knowledge from one domain to another.

EDIT: I took a look at some comments by the OP and it looks like he is talking about a probabilistic case. So my answer does not apply. I'll leave it here for reference.

$\endgroup$
0
$\begingroup$

For the unweighted case, it has recently been shown that there is a quasi-polynomial time algorithm. It is a fresh of the oven result though, you can find a sort of non-expert kind of friendly description of it here or here. And the original paper and even a video of the talk in which Lazlo Babai presented his results.

As mentioned in other answers, it is a hard problem and I have never implemented the solution myself.

Edit: I am not very familiar with Babai's new algorithm and I cannot tell if using a weighted graph is feasible.

$\endgroup$
  • $\begingroup$ The question is asking about weighted graph isomorphism (albeit without defining what that means); Babai deals with the unweighted case. $\endgroup$ – David Richerby Feb 28 '16 at 8:41
  • $\begingroup$ That's true. I am not familiar enough with Babai's new algorithm to tell whether it generalises to the weighted case or not. I'll edit my answer to reflect that. $\endgroup$ – Paco Feb 28 '16 at 8:48
  • $\begingroup$ Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$ – Raphael Jan 4 '17 at 21:41

Your Answer

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