<p>Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley graphs. For instance, shortest paths on circulant graphs (a special case of Cayley graphs) are NP-complete; see "On Routing in Circulant Graphs", Cai et al, COCOON 1999, <a href="http://doi.org/10.1007/3-540-48686-0_36">doi:10.1007/3-540-48686-0_36</a></p>

<p>Of course that doesn't apply to the exact statement of the problem you give (where the group is given as a multiplication table, itself an object of size comparable to the Cayley graph) but it does indicate a need for some care.</p>

CC BY-SA 3.0
2016-06-17T01:01:21.870Z
Interesting, thank you. But in my question the input length is the size of the graph. In particular shortest path can be solved in poly time.
Igor Shinkar
CC BY-SA 3.0
2016-06-16T22:17:21.393Z
2016-06-16T22:17:21.393Z
David Eppstein
<p>What is known about complexity of NP-hard problems on Cayley graphs?</p>

<p>Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input length is the size of the graph. Can we solve NP-complete problems on such graphs (maximum clique/max-cut) in polynomial time?</p>

<p>What about some special cases of groups? For example, $\mathbb{Z}_n$ (a.k.a. circulant graphs) or $\mathbb{Z}_2^{\log(n)}$. That is, the input to the problem is the set of generators (and $1^n$ to represent the size of the graph).</p>

<np-hardness><np-complete>
NP-hardness on Cayley graphs
Igor Shinkar
# NP-hardness on Cayley graphs

(Asked by: username_0 on 2016-06-16)

What is known about complexity of NP-hard problems on Cayley graphs?

Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input length is the size of the graph. Can we solve NP-complete problems on such graphs (maximum clique/max-cut) in polynomial time?

What about some special cases of groups? For example, $\mathbb{Z}\_n$ (a.k.a. circulant graphs) or $\mathbb{Z}\_2^{\log(n)}$. That is, the input to the problem is the set of generators (and $1^n$ to represent the size of the graph).

**Tags:** np-hardness, np-complete

---

## 1 answers

### Answer by username_1 on 2016-06-16. Score: 12

Because the input size (a description of the group and its generators) can be so much smaller than the graph itself, even standard polynomial-time graph optimization problems can become hard on Cayley graphs. For instance, shortest paths on circulant graphs (a special case of Cayley graphs) are NP-complete; see "On Routing in Circulant Graphs", Cai et al, COCOON 1999, [doi:10.1007/3-540-48686-0\_36](http://doi.org/10.1007/3-540-48686-0_36)

Of course that doesn't apply to the exact statement of the problem you give (where the group is given as a multiplication table, itself an object of size comparable to the Cayley graph) but it does indicate a need for some care.

> **Comments:**
> **username_0**: Interesting, thank you. But in my question the input length is the size of the graph. In particular shortest path can be solved in poly time.  

---

