Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
4  
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? – David Richerby Feb 28 at 8:43
    
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. – Yuval Filmus Feb 28 at 19:17
1  
Are you looking for an algorithm that works always or with high probability? If so, probability over what? The choice of weights? – Yuval Filmus Feb 28 at 19:33
    
@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. – Student. Feb 28 at 20:23
1  
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). – D.W. Feb 29 at 7:29
up vote 7 down vote accepted

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.

share|cite|improve this answer
    
I am thinking of a scenario of where number of weights depend on $n$. – Student. Feb 28 at 18:35

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.

share|cite|improve this answer
    
" 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. – Bakuriu Feb 28 at 14:28
4  
No, ILP is not a special case of LP. You can't model an arbitrary ILP as an LP. – Yuval Filmus Feb 28 at 15:20
    
I am thinking of a scenario of where number of weights depend on $n$, this should be easier i think. – Student. Feb 28 at 18:47
    
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. – Yuval Filmus Feb 28 at 19:16
    
@YuvalFilmus I see the issue may be I am not communicating well and I have now updated. – Student. Feb 28 at 19:20

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.

share|cite|improve this answer

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.

share|cite|improve this answer
    
The question is asking about weighted graph isomorphism (albeit without defining what that means); Babai deals with the unweighted case. – David Richerby Feb 28 at 8:41
    
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. – Paco Feb 28 at 8:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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