Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can be formulated as follows.
Problem Given a polynomial $P$, decide whether there is a graph $G$ with the corresponding adjacency matrix $A_G$ such that its characteristic polynomial $\chi_G(\lambda)$ equals the given $P$.
For an arbitrary $P$, it is not always the case that there is a corresponding $A_G$. The naive exhaustive algorithm for the problem uses a basic theorem in algebraic graph theory:
Theorem Let $G=(V,E)$ be a graph with adjacency matrix $A_G$ and $\chi_G(\lambda) = \lambda^n+c_1\lambda^{n-1}+c_2\lambda^{n-2}+\cdots+c_{n-1}\lambda+c_n$, then
(1) $c_1=0$,
(2) $-c_2 = |E|$, and
(3) $-c_3 = \text{twice the # of triangles in G}$.
Now, given $P$, the algorithm goes through every candidate $A_G$ of a corresponding $G$ with $|E|=-c_2$ and number of triangles ($K_3$) equal to $-c_3$. For each $A_G$, compute $\text{det}(A_G - \lambda I)$ and see if it equals the given $P$. If none match, return false. Otherwise, return the $A_G$.
This works, but is clearly not fast. The exhaustive algorithm would work even without the above theorem. Its use makes the search space smaller. What's a fast and more clever algorithm?
Asked By : Juho
Answered By : Jernej
The short answer is no. No quick algorithm for this problem is known.
A big open problem (for at least 50 years) in algebraic graph theory asks about the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.
However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ [1, Proposition 1].
So if there would be a quick solution to your problem, this big open problem would be solved already.
In fact, the theorem that you stated can be further generalized. The $i$'th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c_i = \sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the rank of $H.$
[1] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6115
0 comments:
Post a Comment
Let us know your responses and feedback