Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Are there any algorithms that use the spectral properties of a graph to solve the minimum spanning tree problem?
To clarify further what I have in mind, starting with the Laplacian matrix I want to algebraically arrive at the required set of edges. This is opposed to Prim's or Kruskal's algorithm where the result is obtained by operating on the edges/vertices sets directly.
In short: no, not that I know of and I would be surprised if they exist. For something longer, read on:
I don't think the spectrum of a graph can be of much use in finding an MST. The main reason is this: weights of a graph aren't part of the spectrum of a graph! An MST only makes sense on a weighted graph.
The only thing I see we could try, if all weights are integral, 'unfold' the graph such that all weights are unit-weights (so an edge of weight $32$ becomes $32$ edges and $31$ nodes in them) and mark the original nodes and make a min-cost tree that spans the original edges. After this transformation, the spectrum might contain all relevant info, but this transformation step makes our new graph simply horribly large, so any algorithm based on this will have an awful running time. This is simply a bad idea.
I've never heard of a useful way to 'attach' weights to edges in the adjacency matrix and connect them to the spectral properties, either. It doesn't seem likely to work, although proving a vague method won't work is of course impossible.
Of course, the fact that spectral properties likely aren't useful doesn't mean algebraic methods in general won't work. What is important is that you don't leave the edge weights behind. However, most other algebraic methods are used for exponential time algorithms and I'm not aware anyone has constructed something algebraic for MST.
