<p>Cvetcovic et all in Section 3.3 of "Recent results in the theory of graph spectra" <a href="http://yaroslavvb.com/upload/save/cstheory-cvetcovic-spectra.pdf">goes over </a> algorithms for constructing graphs given spectrum in some special cases</p>

CC BY-SA 2.5
2010-12-12T19:32:00.833Z
2010-12-12T19:32:00.833Z
Yaroslav Bulatov
<p>Even asking whether a graph with a given spectrum exists is a tough question. This is  witnessed by the <a href="https://en.wikipedia.org/wiki/Moore_graph" rel="noreferrer">open problem</a> of determining whether there exists a graph of girth 5 diameter 2 and order 3250 whose spectrum  (if it exists) is known.</p>

CC BY-SA 3.0
2013-10-28T22:57:17.940Z
2016-02-13T05:13:50.050Z
2016-02-13T05:13:50.050Z
Jernej
<p>One other obstacle in defining your question is that the are isospectral (same eigenvalues) but non-isomorphic graphs.  So given a list of eigenvalues in such a case, which graph do you want?  Maybe you just want an algorithm to return one random element of the set of such non-isomorphic graphs?  </p>

CC BY-SA 2.5
2010-12-12T21:17:02.680Z
I was thinking something along the lines of sampling from the space of graphs that are isospectral but this seems like we're quickly descending into a GI equivalent problem (thus my comment above).  For simplicity, we could restrict to all distinct eigenvalues (which, if IIC ensures a unique graph) but I'm really just trying to see what's known or out there.
user834
CC BY-SA 2.5
2010-12-12T22:57:10.673Z
I don't think distinct eigenvalues ensures reconstructibility, here are some spectra of isospectral graphs over 7 nodes http://yaroslavvb.com/upload/save/cstheory-isospectral.png
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-13T02:37:30.463Z
I like the random element formulation. I would be interested to know if it's equivalent to GI. One reason I'm interested in the random element formulation, is the question, raised in my paper with Arora and Steurer on unique games, of whether graphs with certain spectrum can be expanders for small sets. Intuitively, one may hope that a random graph with this spectrum will be the best expander possible for all set sizes, and so insight on reverse spectra may be useful there.
Boaz Barak
CC BY-SA 2.5
2010-12-13T20:09:14.940Z
@Yaroslav: Thank you for that link and thanks for correcting me!
user834
CC BY-SA 3.0
2013-10-30T17:58:51.413Z
@user834: Re: your comment about a GI-equivalent problem. Note that determining isomorphism of graphs with bounded eigenvalue multiplicity (in particular, graphs with no multiple eigenvalues) can be done in polynomial time.
Joshua Grochow
CC BY-SA 3.0
2016-02-13T14:52:13.203Z
Shouldn't this be a comment rather than an answer?
Marc
CC BY-SA 2.5
2010-12-12T21:01:43.300Z
2010-12-12T21:01:43.300Z
dabacon
<p>Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the <a href="http://en.wikipedia.org/wiki/Laplacian_matrix">Laplacian</a>) eigenvalue decomposition (also called the <a href="http://en.wikipedia.org/wiki/Spectral_graph_theory">spectra of a graph</a>).</p>

<p>But what about the reverse problem?  Given $n$ eigenvalues, can one (efficiently) find a graph that has this spectra?</p>

<p>I suspect that in general this is hard to do (and might be equivalent to GI) but what if you relax some of the conditions a bit?  What if you make conditions that there is no multiplicity of eigenvalues?  What about allowing graphs that have "close" spectra by some distance metric?</p>

<p>Any references or ideas would be welcome.</p>

<p><strong>EDIT</strong>:</p>

<p>As Suresh points out, if you allow undirected weighted graphs with self loops, this problem becomes pretty trivial.  I was hoping to get answers on the set of undirected, unweighted simple graphs but I would be happy with simple unweighted directed graphs as well.</p>

CC BY-SA 3.0
2013-01-18T00:51:56.257Z
@user834 I ended up asking a [sampling isospectral (or close to isospectral) question](http://cstheory.stackexchange.com/q/16121/1037) that you mention on dabacon's answer separately without knowing about your question. Have you learnt anymore about this problem since you've asked this question? Would like to hear your insights.
Artem Kaznatcheev
CC BY-SA 2.5
2010-12-11T19:47:37.757Z
I think you might need to modify the question to 'unweighted undirected graphs with no self loops' or something like that ? I can imagine constructing a diagonal matrix with the required eigenvalues and declaring it to be a disconnected graph with weighted selfloops ?
Suresh Venkat
CC BY-SA 2.5
2010-12-12T01:07:40.627Z
Even simpler question (I don't know the answer) is how to construct simple connected graphs whose top few eigenvalues are given
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-12T01:08:57.473Z
You'd think that the Spielman et al spectral sparsification methods should work here. Specifically, take a look at this link: http://arxiv.org/PS_cache/arxiv/pdf/0808/0808.4134v3.pdf
Suresh Venkat
CC BY-SA 2.5
2010-12-12T01:12:38.840Z
An alternative way of stating the question (the version with simple undirected graphs) is: given n real numbers (in some format), decide whether there exists an n×n symmetric 0/1 matrix with zero diagonals such that its n eigenvalues are the given numbers.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-12T12:57:57.647Z
@Yaroslav: I am not sure, but that problem sounds harder to me than the case where all n eigenvalues are given.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-12T16:50:40.883Z
I also like Tsuyoshi's formulation. Maybe it's time for an MO post ;)
Suresh Venkat
CC BY-SA 2.5
2010-12-12T17:41:58.163Z
Tiny observation: If we have no restrictions on the eigenvalues, the problem is really hard (even not include the algorithmic part) since this will implies the (non-)existence to the 57-regular [Moore graph](http://en.wikipedia.org/wiki/Moore_graph), which the eigenvalues are all known.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-12T20:46:47.853Z
@Hsien-Chih - excellent comment !
Suresh Venkat
<ds.algorithms><graph-theory><graph-algorithms><spectral-graph-theory>
Reverse Graph Spectra Problem?
user834
# Reverse Graph Spectra Problem?

(Asked by: username_0 on 2010-12-11)

Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the [Laplacian](http://en.wikipedia.org/wiki/Laplacian_matrix)) eigenvalue decomposition (also called the [spectra of a graph](http://en.wikipedia.org/wiki/Spectral_graph_theory)).

But what about the reverse problem? Given $n$ eigenvalues, can one (efficiently) find a graph that has this spectra?

I suspect that in general this is hard to do (and might be equivalent to GI) but what if you relax some of the conditions a bit? What if you make conditions that there is no multiplicity of eigenvalues? What about allowing graphs that have "close" spectra by some distance metric?

Any references or ideas would be welcome.

**EDIT**:

As Suresh points out, if you allow undirected weighted graphs with self loops, this problem becomes pretty trivial. I was hoping to get answers on the set of undirected, unweighted simple graphs but I would be happy with simple unweighted directed graphs as well.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, spectral-graph-theory
> **Comments:**
> **username_2**: I think you might need to modify the question to 'unweighted undirected graphs with no self loops' or something like that ? I can imagine constructing a diagonal matrix with the required eigenvalues and declaring it to be a disconnected graph with weighted selfloops ?  
> **username_3**: Even simpler question (I don't know the answer) is how to construct simple connected graphs whose top few eigenvalues are given  
> **username_2**: You'd think that the Spielman et al spectral sparsification methods should work here. Specifically, take a look at this link: http://arxiv.org/PS_cache/arxiv/pdf/0808/0808.4134v3.pdf  
> **username_4**: An alternative way of stating the question (the version with simple undirected graphs) is: given n real numbers (in some format), decide whether there exists an n×n symmetric 0/1 matrix with zero diagonals such that its n eigenvalues are the given numbers.  
> **username_4**: @Yaroslav: I am not sure, but that problem sounds harder to me than the case where all n eigenvalues are given.  
> **username_2**: I also like Tsuyoshi's formulation. Maybe it's time for an MO post ;)  
> **username_5**: Tiny observation: If we have no restrictions on the eigenvalues, the problem is really hard (even not include the algorithmic part) since this will implies the (non-)existence to the 57-regular [Moore graph](http://en.wikipedia.org/wiki/Moore_graph), which the eigenvalues are all known.  
> **username_2**: @Hsien-Chih - excellent comment !  
> **username_1**: @user834 I ended up asking a [sampling isospectral (or close to isospectral) question](http://cstheory.stackexchange.com/q/16121/1037) that you mention on dabacon's answer separately without knowing about your question. Have you learnt anymore about this problem since you've asked this question? Would like to hear your insights.  

---

## 3 answers

### Answer by username_3 on 2010-12-12. Score: 11

Cvetcovic et all in Section 3.3 of "Recent results in the theory of graph spectra" [goes over](http://yaroslavvb.com/upload/save/cstheory-cvetcovic-spectra.pdf)  algorithms for constructing graphs given spectrum in some special cases


---

### Answer by username_6 on 2013-10-28. Score: 11

Even asking whether a graph with a given spectrum exists is a tough question. This is witnessed by the [open problem](https://en.wikipedia.org/wiki/Moore_graph) of determining whether there exists a graph of girth 5 diameter 2 and order 3250 whose spectrum (if it exists) is known.


---

### Answer by username_7 on 2010-12-12. Score: 5

One other obstacle in defining your question is that the are isospectral (same eigenvalues) but non-isomorphic graphs. So given a list of eigenvalues in such a case, which graph do you want? Maybe you just want an algorithm to return one random element of the set of such non-isomorphic graphs?

> **Comments:**
> **username_0**: I was thinking something along the lines of sampling from the space of graphs that are isospectral but this seems like we're quickly descending into a GI equivalent problem (thus my comment above).  For simplicity, we could restrict to all distinct eigenvalues (which, if IIC ensures a unique graph) but I'm really just trying to see what's known or out there.  
> **username_3**: I don't think distinct eigenvalues ensures reconstructibility, here are some spectra of isospectral graphs over 7 nodes http://yaroslavvb.com/upload/save/cstheory-isospectral.png  
> **username_8**: I like the random element formulation. I would be interested to know if it's equivalent to GI. One reason I'm interested in the random element formulation, is the question, raised in my paper with Arora and Steurer on unique games, of whether graphs with certain spectrum can be expanders for small sets. Intuitively, one may hope that a random graph with this spectrum will be the best expander possible for all set sizes, and so insight on reverse spectra may be useful there.  
> **username_0**: @Yaroslav: Thank you for that link and thanks for correcting me!  
> **username_9**: @user834: Re: your comment about a GI-equivalent problem. Note that determining isomorphism of graphs with bounded eigenvalue multiplicity (in particular, graphs with no multiple eigenvalues) can be done in polynomial time.  
> **username_10**: Shouldn't this be a comment rather than an answer?  

---

