[Solved]: What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

Problem Detail: 

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

3.2K people like this

 Download Related Notes/Documents