Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2015
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912075342675968 |
|---|---|
| author | Prolubnikov, Alexander |
| author_facet | Prolubnikov, Alexander |
| contents | The graph isomorphism problem is considered. We assign modified $n$-variable characteristic polynomials for graphs and reduce the graph isomorphism problem to the problem of the polynomials isomorphism. It is required to find out, is there such a numbering of the second graph's vertices that the polynomials of the graphs are equal.
We present algorithms for the graph isomorphism problem that use the reduction. We prove the propositions that justify the possibility of numerical realization of the algorithms for the general case of the graph isomorphism problem. The algorithms perform equality checking of graphs polynomials. We show that probability of obtaining a wrong solution of the graph isomorphism problem by comparing values of graph polynomials is negligible if the mantissa length is sufficiently large.
Since, for a graph on $n$ vertices, the graph polynomial has $2^n$ coefficients, its value at some point cannot be evaluated directly for large enough $n$. We show that we can check the equality of the polynomials at some points without direct evaluation of the polynomials values at these points. We prove that it is required $O(n^4)$ elementary machine operations and machine numbers with mantissas length $O(n^2)$ to check equality of the values for the graphs on $n$ vertices.
For the worst, it needs an exponential from $n$ time to solve the graph isomorphism problem instance using the presented approach, but in practice, it is efficient even for well known computationally hard instances of the graph isomorphism problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1512_03139 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction Prolubnikov, Alexander Discrete Mathematics F.2.1; G.1.3 The graph isomorphism problem is considered. We assign modified $n$-variable characteristic polynomials for graphs and reduce the graph isomorphism problem to the problem of the polynomials isomorphism. It is required to find out, is there such a numbering of the second graph's vertices that the polynomials of the graphs are equal. We present algorithms for the graph isomorphism problem that use the reduction. We prove the propositions that justify the possibility of numerical realization of the algorithms for the general case of the graph isomorphism problem. The algorithms perform equality checking of graphs polynomials. We show that probability of obtaining a wrong solution of the graph isomorphism problem by comparing values of graph polynomials is negligible if the mantissa length is sufficiently large. Since, for a graph on $n$ vertices, the graph polynomial has $2^n$ coefficients, its value at some point cannot be evaluated directly for large enough $n$. We show that we can check the equality of the polynomials at some points without direct evaluation of the polynomials values at these points. We prove that it is required $O(n^4)$ elementary machine operations and machine numbers with mantissas length $O(n^2)$ to check equality of the values for the graphs on $n$ vertices. For the worst, it needs an exponential from $n$ time to solve the graph isomorphism problem instance using the presented approach, but in practice, it is efficient even for well known computationally hard instances of the graph isomorphism problem. |
| title | Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction |
| topic | Discrete Mathematics F.2.1; G.1.3 |
| url | https://arxiv.org/abs/1512.03139 |