<p>The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. <a href="https://web.eecs.umich.edu/~pettie/matching/Harvey-maximum-matching-j-version.pdf" rel="nofollow noreferrer">matchings</a> and <a href="https://arxiv.org/abs/cs/0008011" rel="nofollow noreferrer">shortest paths</a>).</p>

<p>However, while the fast Fourier transform algorithm implies several other near-linear-time <em>algebraic</em> algorithms including polynomial multiplication, multi-point evaluation, interpolation, etc., I do not know its application to any graph problem yet.</p>

<blockquote>
  <p>What are applications of the fast Fourier transform to graph problems?</p>
</blockquote>

<p>Actually, applications other fast algebraic algorithms (except fast matrix multiplication) are also welcomed.</p>

CC BY-SA 3.0
2018-02-20T04:09:24.743Z
My rough take is that FFT is essentially about 1D structures, whereas matrix multiplication is (in some fairly precise sense) its "2D" analogue. Graphs are definitely not 1D, and one can argue they are 2D because they about pairwise relationships (viz. the adjacency matrix). This analogy isn't perfect, nor precise, but perhaps explains at a high level why there are more applications of matrix multiplication than FFT to graphs. I'll be interested to see if there are examples!
Joshua Grochow
CC BY-SA 3.0
2018-02-20T20:48:29.307Z
FFT is used for exponential-time algorithms for NP-hard problems on graphs. See, for example, 1. Theorem 7.8 in http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf 2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.3413&rep=rep1&type=pdf  3. http://people.csail.mit.edu/rrw/presentations/subset-conv.pdf
Alex Golovnev
<ds.algorithms><graph-algorithms>
Graph-related applications of the fast Fourier transform (and other algebraic algorithms)
Thatchaphol
# Graph-related applications of the fast Fourier transform (and other algebraic algorithms)

(Asked by: username_0 on 2018-02-19)

The fast matrix multiplication algorithm is useful for numerous graph problems (e.g. [matchings](https://web.eecs.umich.edu/~pettie/matching/Harvey-maximum-matching-j-version.pdf) and [shortest paths](https://arxiv.org/abs/cs/0008011)).

However, while the fast Fourier transform algorithm implies several other near-linear-time *algebraic* algorithms including polynomial multiplication, multi-point evaluation, interpolation, etc., I do not know its application to any graph problem yet.

> What are applications of the fast Fourier transform to graph problems?

Actually, applications other fast algebraic algorithms (except fast matrix multiplication) are also welcomed.

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: My rough take is that FFT is essentially about 1D structures, whereas matrix multiplication is (in some fairly precise sense) its "2D" analogue. Graphs are definitely not 1D, and one can argue they are 2D because they about pairwise relationships (viz. the adjacency matrix). This analogy isn't perfect, nor precise, but perhaps explains at a high level why there are more applications of matrix multiplication than FFT to graphs. I'll be interested to see if there are examples!  
> **username_2**: FFT is used for exponential-time algorithms for NP-hard problems on graphs. See, for example, 1. Theorem 7.8 in http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf 2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.192.3413&rep=rep1&type=pdf  3. http://people.csail.mit.edu/rrw/presentations/subset-conv.pdf  

---

## 0 answers

