Re: Is graph isomorphism in P?

On 21 Lug, 05:18, Proginoskes <CCHeck...@xxxxxxxxx> wrote:
This is a bad way of checking whether a problem is in P or not. For
instance, if you choose a random matrix, then the vast majority of the
time you can find its clique size in polynomial time. (This has been
proven formally, btw.) This is because there are a small number of
graphs which are "pathological", so most of the time, you can solve NP-
complete problems in polynomial time.

This is also why the average running time is not a good measure; over
99% of the time, the running time is polynomial, which leads to a
polynomial average running time.

In Theoretical computer science, who works on Graph Isomorphism
problem, knows that, for the world's fastest isomorphism testing
program, that is Nauty, the worst cases are "the bipartite point/line
graphs of projective planes. Even for a plane of order 25, with 651
x 2 vertices it becomes prohibitively difficult for nauty."

So, if you see on what I've written in the previous posts
in this newsgroup, you have enough informations to generate
adjacency matrices of bipartite graphs that are the "worst-case"
for nauty. You don't believe?
Well, consider a set of Steiner's triples, called a, and apply
these octave instructions:

a=[1,0,0,1,0,1;0,1,0,1,0,1;1,1,0,0,1,0;0,0,1,0,1,1;1,1,1,0,0,0;0,0,1,1,1,0]
zero6=round(randerr(6,6,0));
a6=[zero6,a;a',zero6];
zero12=round(randerr(12,12,0));
a12=[zero12,a6;a6',zero12];
zero24=round(randerr(24,24,0));
a24=[zero24,a12;a12',zero24];
zero48=round(randerr(48,48,0));
a48=[zero48,a24;a24',zero48];
zero96=round(randerr(96,96,0));
a96=[zero96,a48;a48',zero96];
zero192=round(randerr(192,192,0));
a192=[zero192,a96;a96',zero192];
zero304=round(randerr(304,304,0));
a304=[zero304,a192;a192',zero304];
zero384=round(randerr(384,384,0));
a384=[zero384,a192;a192',zero384];
A=a384(randperm(768),randperm(768));
B=A(randperm(768),randperm(768));

now A and B are a worst-case of 768x768 adjacency matrices of
bipartite graphs for which is not know a Polinomial-time
algorithm and it has rows and columns random permutated.

The same code can be adapted for every Steiner's triples.
Especially in this sense I'm testing my algorithm.

Simple. Try all 400! permutations of the vertices of the first graph
and see whether you get the second graph (which also takes a constant
number of operations: m*O(n) = O(n^3) = O(400^3) = O(1), which is
constant time). If any work, return YES; otherwise, return NO. Since
400! is a constant, this is a constant-time algorithm.

Ok and now please let me know where I can find:
1)an hard disk enough large in order to save in it 400! permutated
matrices
2)a bit of immortality so that I can wait that my notebook generates
all 400! permutations.

Anyway, I've no problem to solve 600x600 or 1000x1000 MI istances,
let me some hours and I will post here:http://isoproblem.freeforums.org/viewforum.php?f=1
also a 600x600 MI problem on adjacency matrix of
bipartite graphs.

Once again, I'm not interested in "random" graphs, since results
concerning them are already known and established.

I'm not interested only to random graph in the stricly sense,
answer about this poit is already written upon.

It's a shame that Graph Isomorphism isn't NP-complete, because what I
would do then would be to ask you to look at the graphs which arise
from transforming instances of 3-SAT into Graph-Isomorphism, which are
the graphs that everyone (concerned with P vs. NP, that is) is really
interested in. Random graphs won't do it.

There are many variants for the graph isomorphism problem that are
NP-complete, one of them is "GRAPH ISOMORPHISM WITH RESTRICTIONS"
and admits trasformation from 3SAT see "A. LUBIW, Some NP-complete
problems similar to graph isomorphism, SIAM J. Comput. 10 (1981),
11-21."

Shortly, you could generate 3SAT istances whose turing-equivalent
"GRAPH ISOMORPHISM WITH RESTRICTIONS" problem has |H|=1 so that
you can obtain a "graph isomorphism with restricions" turing-
equivalent
to the still opened graph isomorphism problem.


To show that your algorithm is polynomial-time, you need to find
constants k, C, and n, so that your algorithm (running on two graphs
with N vertices) requires at most C*N^k steps, where N >= n, and
determines correctly whether there is an isomorphism. That requires a
specific description of the algorithm and a running time analysis and
a proof of correctness.

It is is what I've done but I've not placed online, more formally
I've:
1)a mathematical algorithm's correctness proof.
2)a mathematical analysis of the infinite order of the set of
functions
(which describes calculus time of each procedure) involved in the
algoritm.

Fra

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Since graph isomorphism is a long studied problem with no known ... my algorithm is more than likely flawed. ... Given two truly random graphs of any significant size (say, ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Since graph isomorphism is a long studied problem with no known ... For 2*D iterations, update each vertex's hash value, by hashing it with it's neighbor's hash values, and the iteration number. ... does that mean that you first XOR all a node's neighbors' current hashes together and then hash the result in with the node's current hash and the iteration number? ... It generates the same hash for each node of two non-isomorphic graphs if the two graphs have the same number of nodes and all the nodes on the graphs have the same degree. ...
    (sci.crypt)
  • Re: Is graph isomorphism in P?
    ... time you can find its clique size in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... saved that excerpt), from a DMANET discussion. ... Certainly, if you can do graph isomorphism for bipartite graphs, you ...
    (sci.math)
  • Re: A question in graph theory
    ... linearly ordering all Graphs.? ... there are only finitely many graphs ... graph isomorphism problem, which is suspected to be infeasible. ... determined in polynomial time. ...
    (sci.math)
  • Re: A question in graph theory
    ... linearly ordering all Graphs.? ... there are only finitely many graphs ... If what you mean is an algorithm which, given the number 1729, ... graph isomorphism problem, which is suspected to be infeasible. ...
    (sci.math)
Loading