8
$\begingroup$

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).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

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

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Igor Shinkar
    Jun 17, 2016 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.