Thread: Detecting "Crossing" in GraphIsomorphism

Two graphs G, H. Assume there is an algorithm which can only detect planar graph isomorphism. This means the algorithm gets confused if G and H have different “crossing” which is allowed in “Simple graph”. The algorithm says both G and H are isomorphic to each other when there is no difference between G, H except having different “crossing” which is wrong.
Assume, G and H are isomorphic to each other without considering “crossing” of graphs (though they have different “crossing” which is not considered in the assumption means there is no difference between G, H except having different “crossing” ). For G, make matrix (two dimensional) D_g which consists “All-Pair Shortest Path” (APSP) by a polynomial time algorithm (such algorithm exists).Do same for H and get D_h. The difference between G and H can be detected in D_g , D_h . The argument is given below.

For simplicity, assume, both G, H are exactly same except on vertices a, b, c, d. In G, a connected with b, c connected with d. But in H, a connected with c, b connected with d and both pair create two “crossing”. In G, the shortest distance between a, c is more than 1 whereas in H it is exactly 1. These differences are detected in D_g , D_h .
Set A_i= {a, b, c, d} is the set where difference was noticed. Every A_j creates a difference in D_g , D_h .If A is the union of all A_j , then total |A| difference exists in D_g , D_h . If D_g , D_h are compared(polynomial time), it can be said that G, H are not isomorphic.

A confusion may arise if “APSP Matrix” (e.g. D_g , D_h ) is started from different vertices. This can be solved maintaining some fixed rules and row-column operation simultaneously. APSP can be found by BFS in polynomial time also, I guess.

Procedure:
Two “Simple Graph” G, H are Planar graph-wise isomorphic (i.e. invariants are same except “Crossing”).
1.Get AllPairShortestPath(APSP) matrices of graph G,H ( say g[i][i], h[i][i] respectively).
2. Compare both matrices using a function F, if F returns true, graphs are isomorphic.
The comparing function F works as below-
[I]F ( g[i][i] , h[i] ){

1. [I]Sort elements of g[1][i] , h[1][i], g[i][1], h[I][1] in ascending order. // may omit…
2. //their valency(degree) should be same.
3. for (j=0; j<i; i++) { /* j row, k column. */
4. for(k=0; k<i; j++) {
5. if(g[j][k]== h[j][k]){
6. K++;}
7. else {
8. e = k;
9. if (D[k]>2)
10. return false; /*each column can’t participate in “interchanging” more than twice */
11. for (l=k+1;l<I; l++){
12. If(g[j][k]== h[j][k]) {
13. Swap e th column and row with l th column and row;
14. D[e]=D[e]+1;
15. l=l+1;} // break
16. } } }} }

** step 1 might be omitted…it was not used in the example.

these are images for example,
Image codes: GI 050914 Page 3

Image codes: GI 050914 Page 4

Image codes: GI 050914 Page 5

Image codes: GI 050914 Page 6

The interesting thing about the graph isomorphism problem is that it isn't NP-complete, but it doesn't seem to be P either, so it's much more likely that it can be solved quickly than the various NP-complete problems.

That said, I think this algorithm is going to run in to the same problem as the other one. When you have your two NxN matrix, you're going to have to match them up, and for very large graphs with lots of similar vertices, that's going to take time. (Just checking every permutation would take N! checks, but it's very likely to take less than that in practice.)

If you want a P algorithm for graph isomorphism, you're going to have to prove (rigorously) that:
- The matrices generated are unique among graphs (probably not too hard as an adjacency matrix is unique)
- That your algorithm can always match the matrices, or conclude that they don't match, in polynomial time (not so trivial)

Or find an algorithm that bypasses matrices altogether (although then you'll probably end up doing something equivalent to the vertices anyway).

(BTW planar graph isomorphism is solvable in polynomial time.)

Magi_master.... have you tried two regular graphs(e.g. both 8 vertices with all having degree 3 or something like that..)??get APSP matrices and let me know if the above does not work.

About "matching": well, "APSP" should be be filled in certain order.like-
1.The first row should be the vertex of the degree which is least in the graph(if more than one,take any).say,the vertex is x.
2.After the first row,next all row's vertices are the adjacent of first row,which means 1st level of the 1st row's vertex (which is x),if that is finished,then 2nd level of x...almost like BFS.
3.In a row,vertices should be according to their degree(probably not needed).

In this method ,APSP matrices would look different if they are not isomorphic but same if they are.

It should be noticed that same graph would look different if one starts taking input from different vertex(or labeling??! ) but if you do some row column operation it would look exactly same.If they are not iso: , they look different despite the operation.
after getting D_g , D_h , change the 1st row of D_g according to D_h (column will be changed) .Do the same change for rows.for example, for 1st row of D_g ,if 2nd and 3rd column needs to interchange to become the same as the 1st row of D_h, interchange 2nd ,3rd column as well.

if in both matrices, 1st row looks same, then matching starts.Matrices have "0"s in diagonal, and upper triangular has same elements of lower triangular.this matching should take O(n*n) time.

Or I am missing something very"trivial"??
well, in that case a counterexample would help!!
I have shown some reasons in this thread in both posts .If you think it does not work disproof above argument or provide counterexample!
That would be helpful.

You really ought to try that yourself, since it's your algorithm. Better yet would be to write yourself a program to generate several large graphs that you know are either isomorphic or not.

Originally Posted by jim198810

but if you do some row column operation it would look exactly same

That's exactly the problem. I know that the APSP matrix of two isomorphic graphs will be the same. (I'm not 100% sure that they'll always be different for nonisomorphic graphs, but it seems reasonable.) What you need to rigorously prove is that "some row operations" is always "a polynomial number of deterministic row operations."

You say "change the 1st row of D_g according to Dh" but that isn't specific enough to actually implement. What do you do if there are multiple possibilities for that first change and several rows later you discover that the rest of the two matrices don't fit together? If you just stop there, can you prove that that first decision never needs to be revisited? If you go back and try the other possibilities, can you prove that it will still run in polynomial time?

@ Mgi_Master, ...... Of-course i have tried , I told you so you can understand the process I described.



Yep, you are spot on the problem.I have yo come up with proof that guarantees that the algo works!!



It is actually specific , i think you have not understand it yet.In the case of multiple possibilities,shift each of them to 1st column..t_x< (V_G/2) +1 times..with same degree x,where V_G=n..each time to order each of them ,it would take n steps and to check n(n-1)/2 entries of APSP matrices after ordering, since APSP matrix "preserves order"(this is what I have to prove).So, the complexity I am hoping for is O(n*n*n*n).

It might be my bad English, that confuses you...Sorry for that!!

If I can't follow the description, I won't be able to apply it to a test problem. It would be helpful if you could either walk through a small example (it doesn't have to be a 3-regular graph or anything) or rewrite your algorithm in pseudocode. Plain English isn't all that great for describing such things (almost) no matter how good of a writer you are.

Any counterexample ???

You should use the [ code ] tag so you can indent your code. You also need to be a lot more careful about using notation consistently (or avoiding typos, it's hard to tell). For example, what does h[][i] and h[1] mean?

Anyway, I'm not looking for counterexamples right now. If you clean your code up enough, I might, but I've got other things I need to be working on. In the mean time, you should be trying everything you can to find counterexamples yourself, including getting the computer to try large random examples of both isomorphic and non-isomorphic graphs.

Sorry for that,.... I should be more careful , I have edited ...pls chk and let me know if you have any confusion. One thing is that The code is not exact... It just give you a Rough Idea....Have you understood the example???? That's important.


Thanks for working on Counterexample.
**I have 2 lemmas for the Algo: , I might add them later...after checking...

You should still use the code tag. Indentation is important in C-style syntax to denote what bits of code are in what loops. It's really hard to keep up with all that otherwise.

Code:

F ( g[i][i] , h[i] ){
  Sort elements of g[1][i] , h[1][i], g[i][1], h[i][1] in ascending order. // may omit…
  //their valency(degree) should be same.

  for (j=0; j<i; i++) { /* j row, k column. */
    for(k=0; k<i; j++) {
      if(g[j][k]== h[j][k]){
        k++;
      } else {
        e = k;
        if (D[k]>2)
          return false; /*each column can’t participate in “interchanging” more than twice */

        for (l=k+1;l<I; l++){
          if(g[j][k]== h[j][k]) {
            Swap e th column and row with l th column and row;
            D[e]=D[e]+1;
            l=l+1;
          } // break
        } 
      } 
    }
  } 
}

First, it may not be possible to sort both the first row and first column at the same time while keeping the diagonal elements on the diagonal. (I'm not completely sure it isn't, but it's something you'd have to prove or point to a proof of to be able to use.)

Second, I think you've left out some important details, such as what happens to the variable e when swapping things in the innermost loop.

when swapping ends , e has nothing to do.Before next swapping e changes.

forget the pseudo-code, read the below instruction and try the example.



Two graph G, H. Their All pair shortest path matrices are g, h respectively. |G|, |H| are their total vertices number.

1. The valency(degree) of the 1^st row in both g and h should be same(since, each row represents a vertex in a APSP matrix)
2. Sort the 1^st row of g, h in ascending order and also in a way so that all diagonal elements are ‘0’(if you interchange i column with l to keep the order, you have to interchange the i row with l th row to keep the ‘0’in diagonal )
3. Start comparing h with g(each element in row, one by one…).
4. If for ith row jth column, h[i][j]!=g[i][j], look for g[i][j] in the same row i, if found in l< |h|, swap the column l with column j.
5. After permuting the whole h with respect to g, compare g ,h. if g=h then G, H isomorphic.

*each column can’t participate in “interchanging” more than twice.


now see the below example,



Image codes: GI 050914 Page 3

Image codes: GI 050914 Page 4

Image codes: GI 050914 Page 5

Image codes: GI 050914 Page 6



check the above procedure with examples, ask anything that confuses you.

You need to be more precise when spelling out algorithms. Step 4 isn't clearly written and you're mixing up indices. Do you mean: If h[i][j] != g[i][j] look for a k such that h[i][j] == g[i][k] and swap row and column j and k? Also, you put a footnote, but didn't attach it to anything. I assume it's supposed to be attached to step 4? Your example does not keep the 0s in the diagonal. Does that only apply to step 2?

1.Do you mean: If h[i][j] != g[i][j] look for a k such that h[i][j] == g[i][k] and swap row and column j and k?


no

such that h[i][k] == g[i][j] and swap row and column j with k in h.

2. Ignore the footnote now, you will get it later

3."Your example does not keep the 0s in the diagonal."

whenever you interchange j column with k , you have to interchange the j row with k row to keep the ‘0’in diagonal.

can you be precise in which page and matrix it does not??



** probably, I didn't save document before I closed it, so 'i' become 'I' and such mistake remained when I copied it!!

In your page 5, you swap several rows, then several columns. The 0s end up back on the diagonal, which might be OK, but it'd be better to avoid that complication.

I'm not going to ignore footnotes. Algorithms must be precise and complete. Otherwise there's no way to say what they'll do. Those aren't details. They can change the final outcome.

Just Give me a counter example(the footnote has nothing to do with counter example, its "counting" thing).

Have you tried constructing any yourself?

Tried on some regular graph.... no counterexample so far.......learning Martin Furer's counterexample construction for W-L method... but it would be helpful if anyone can come up with a counterexample.

I can't think of any easy counterexamples right now, but I can mention how this algorithm might fail, which might give you some ideas on where to look for counterexamples. It might also give you an idea of some of the things you'd have to prove to prove that this algorithm always works.
- Find two graphs that are not isomorphic, but have the same all-pairs-shortest-path matrix
- Find a way of rearranging a graph so that the algorithm makes too many swaps when comparing matrices
- Find a way of rearranging a graph so that the algorithm finishes, but doesn't manage to make the matrices match

I don't know whether or not it's possible to have two non-isomorphic graphs with the same all-pairs-shortest-patch matrices, but I don't know how to prove it's impossible off the top of my head either.

"Find two graphs that are not isomorphic, but have the same all-pairs-shortest-path matrix"

chk the proof-

Image codes: Pages from f050914

"Find two graphs that are not isomorphic, but have the same all-pairs-shortest-path matrix"

chk the part a (not b !) in below image-

Image codes: Pages from f050914

I don't buy that as a proof for a couple of reasons. (Note, I'm not saying the conclusion is necessarily wrong, but I don't think you've proven it.)
- g cannot arbitrarily be an identity element. An identity element of a group has to satisfy certain properties. Namely, for any other element h, g*h = h*g = h. I think this is salvageable though. Change A to the set of permutation matrices, not the set of permutations of g. Then you'd be looking at a*g and a*h.
- 2.a.i. doesn't make sense. What does "strats on vertex u" mean? Also, h will not generally be the same as g. Instead, you need to show that there's some permutation a so that a*h = g.
- 2.a.ii. does not prove anything about the graph h. All it says is that because the APSP matrices are the same, the APSP matrices are the same.
- The conclusion you draw from 2.a.ii. is actually just the contrapositive of 2.a.i. which doesn't need further proof if 2.a.i. is true. (The contrapositive of a true statement is always true.) Instead, you need to show that the implication goes the other way.

"What does "strats on vertex u" mean?"

..... it means that if both graphs are isomorphic , then both have a vertex, say u, if you start APSP from that vertex then Both APSP of graphs will loke same .

"a.ii. does not prove anything about the graph h. All it says is that because the APSP matrices are the same, the APSP matrices are the same."


....... No mate, it says that if two graphs are not isomorphic than their APSP matrices can't rearranged to each other(if G!=H theng can't be permutaed, so g=h).


"The conclusion you draw from 2.a.ii. is actually just the contrapositive of 2.a.i. which doesn't need further proof if 2.a.i. is true."

.. I thought if I need to prove a "if and only if" statement, i need to do it both way... not sure about "The contrapositive of a true statement is always true.Instead, you need to show that the implication goes the other way" can you please explain a little bit elaborately ??

...and your beginning... "Change A to the set of permutation matrices, not the set of permutations of g. "

...it is!! if you permute g (keeping diagonal'0') a is what you want!!

The thing about the permutation matrices is only a minor technical matter. The other errors are more serious.

Yes, you need to show both ways with an "if and only if," but you haven't done that. You need to show "A implies B" and "B implies A." Instead, you tried to show "A implies B" and "(not B) implies (not A)." That last one is the contrapositive of "A implies B" and isn't equivalent to "B implies A".

I see what you meant with strats (typo - starts), but that's not true. The APSP algorithms do not visit nodes in a deterministic order. If you rearrange all the nodes besides the starting node, you'll still get a permuted matrix.

Finally, you have to prove that two nonisomorphic graphs will always have different APSP matrices. So far you've only assumed that.

"you tried to show "A implies B" and "(not B) implies (not A)."

.... I showed A implies (NOT B) is not possible. you should check the first statement of (ii)


"The APSP algorithms do not visit nodes in a deterministic order. "



... you can do that in deterministic way , but that is not the point. Point is if you start from same vertex you will get the same matrix. permutation can be rearranged to get same thing.


"Finally, you have to prove that two nonisomorphic graphs will always have different APSP matrices. So far you've only assumed that."

??!!

You're assuming too much. Obvious doesn't cut it in a formal proof.

You cannot just say two matrices are the same if they're permutations of each other. If you have to check every permutation, that's not polynomial time. If you want to say that you can show equality in polynomial time, you'll have to prove that. Similarly, if you want to say that two nonisomorphic graphs can never give the same APSP matrix, you'll have to prove that. (Or at least reference an existing proof.)

You also need to be very careful about your logic. If you want to show A and (not B) are equivalent, you need to show A implies (not B) and (not B) implies A. There are a lot of subtle ways to get that wrong, such as by trying to prove A implies (not B) and B implies (not A), which does not prove what you're trying to prove.

"You're assuming too much"
- If I assume, then I say that.

Originally Posted by jim198810

"you tried to show "A implies B" and "(not B) implies (not A)."

.... I showed A implies (NOT B) is not possible. you should check the first statement of (ii)

- you have not understood it yet.


"You cannot just say two matrices are the same if they're permutations of each other. If you have to check every permutation, that's not polynomial time."

...I really dont know how to comment...the proof I gave was a "existence proof", not a proof to show that it was a polynomial time...how you linked that. That is a different issue.



"If you want to show A and (not B) are equivalent, you need to show A implies (not B) and (not B) implies A. There are a lot of subtle ways to get that wrong, such as by trying to prove A implies (not B) and B implies (not A), which does not prove what you're trying to prove."

- I could be wrong, and there are "a lot of subtle ways" to get something wrong, but I just fail to see your reason...I am going to stop here.

And I'll just say that your point 2 does not prove anything.