<p>For your first question: yes, it is NP-complete. The complete graph is the Cayley graph of <em>any</em> group, if you take the entire group (say, except the identity, but that would just add a self-loop at every vertex) as the generating set. Then CLIQUE is a particular instance of your problem. </p>

<p>A more interesting question might be to restrict Cayley subgraph isomorphism to Cayley graphs where only a minimal, or say $O(\log|G|)$-sized, generating set is used.</p>

<p>For your second question, the answer is also yes, because not only is Code Equivalence similar to Graph Isomorphism, but GI reduces to Code Equivalence. Essentially the same reduction (due to Petrank and Roth) gives a reduction from Subgraph Isomorphism to Subcode Equivalence.</p>

CC BY-SA 3.0
2013-10-15T18:59:32.867Z
Does this result hold for structured graphs as well? For instance $G$ is tensor or cartesian product of graphs $g$ and the evidence of $g$ in $H$ is easy to find. For instance $g$ could be a path or a cycle.
Turbo
CC BY-SA 3.0
2013-10-15T19:21:50.390Z
I don't know. However, the examples you give of $g$ are not easy to find: special cases where $g$ is a path/cycle include Hamiltonian path/cycle, which is NP-complete (even without using tensor or cartesian products). I recall there was some result on when a family $\{G_n\}$ of graphs is easy to find as an induced subgraph, but I don't recall the reference.
Joshua Grochow
CC BY-SA 3.0
2013-10-15T19:37:17.383Z
I meant say path or cycle in H when it is easy to find. I understand what you are saying and if you have the link please provide if you can.
Turbo
CC BY-SA 3.0
2013-10-15T20:16:45.633Z
Does the problem remain NP-complete if diameters of $G$ and $H$ are fixed, say $diameter=2$ or a fixed $k$? Can one expect a Ramsey type theorem for diameter $2$ graphs $G$ where one asks "How large should a fixed $k$-diameter graph $d$-regular graph $H$ be for it to have a fixed $k$-diameter graph $G$ of vertex count $n_G$?"?
Turbo
CC BY-SA 3.0
2013-10-15T20:22:53.720Z
Again $G$ and $H$ are both regular.
Turbo
CC BY-SA 3.0
2013-10-15T20:30:20.557Z
I will post as new question.
Turbo
CC BY-SA 3.0
2013-10-15T23:13:13.950Z
It looks like diameter follows from your answer. not thinking correct today!
Turbo
CC BY-SA 3.0
2013-10-15T17:58:54.563Z
2013-10-15T17:58:54.563Z
Joshua Grochow
<p>Let $G$ be an undirected Cayley graph over an abelian group. Let $H$ a regular graph whose independence number and chromatic number are known. Let $inj(G,H)$ be the number of injective homomorphisms from $G$ to $H$. It is known <em>SUBGRAPH ISOMORPHISM</em> is NP-complete. Consider the <em>CAYLEY SUBGRAPH ISOMORPHISM</em> problem: </p>

<p>Given an undirected Cayley $G$ and a regular $H$, is inj(G,H)>0?</p>

<p>Is the above problem NP-complete?</p>

<p>Since linear codes are abelian, I am extending the question. Given two $[n_i,k_i,d_i]$ linear codes $C_i$ for $i=1$ and $2$ and $n_1&lt;n_2$, is deciding $C_1\cong D \subset C_2$ NP-complete? Note that code isomrphism is similar to graph isomorphism.</p>

CC BY-SA 3.0
2013-10-15T16:30:51.897Z
Cayley graphs are edge-labeled. When you talk of homomorphisms from $G$ to $H$, do you mean that edge labels are ignored?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2013-10-15T17:04:36.253Z
just ignore them or use them if they are useful.
Turbo
<graph-theory><graph-isomorphism>
Cayley subgraph isomorphism and complexity of linear subcode decision
Turbo
# Cayley subgraph isomorphism and complexity of linear subcode decision

(Asked by: username_0 on 2013-10-15)

Let $G$ be an undirected Cayley graph over an abelian group. Let $H$ a regular graph whose independence number and chromatic number are known. Let $inj(G,H)$ be the number of injective homomorphisms from $G$ to $H$. It is known *SUBGRAPH ISOMORPHISM* is NP-complete. Consider the *CAYLEY SUBGRAPH ISOMORPHISM* problem:

Given an undirected Cayley $G$ and a regular $H$, is inj(G,H)>0?

Is the above problem NP-complete?

Since linear codes are abelian, I am extending the question. Given two $[n\_i,k\_i,d\_i]$ linear codes $C\_i$ for $i=1$ and $2$ and $n\_1

**Tags:** graph-theory, graph-isomorphism

> **Comments:**
> **username_1**: Cayley graphs are edge-labeled. When you talk of homomorphisms from $G$ to $H$, do you mean that edge labels are ignored?  
> **username_0**: just ignore them or use them if they are useful.  

---

## 1 answers

### Answer by username_2 on 2013-10-15. Score: 2 | Accepted answer

For your first question: yes, it is NP-complete. The complete graph is the Cayley graph of *any* group, if you take the entire group (say, except the identity, but that would just add a self-loop at every vertex) as the generating set. Then CLIQUE is a particular instance of your problem.

A more interesting question might be to restrict Cayley subgraph isomorphism to Cayley graphs where only a minimal, or say $O(\log|G|)$-sized, generating set is used.

For your second question, the answer is also yes, because not only is Code Equivalence similar to Graph Isomorphism, but GI reduces to Code Equivalence. Essentially the same reduction (due to Petrank and Roth) gives a reduction from Subgraph Isomorphism to Subcode Equivalence.

> **Comments:**
> **username_0**: Does this result hold for structured graphs as well? For instance $G$ is tensor or cartesian product of graphs $g$ and the evidence of $g$ in $H$ is easy to find. For instance $g$ could be a path or a cycle.  
> **username_2**: I don't know. However, the examples you give of $g$ are not easy to find: special cases where $g$ is a path/cycle include Hamiltonian path/cycle, which is NP-complete (even without using tensor or cartesian products). I recall there was some result on when a family $\{G_n\}$ of graphs is easy to find as an induced subgraph, but I don't recall the reference.  
> **username_0**: I meant say path or cycle in H when it is easy to find. I understand what you are saying and if you have the link please provide if you can.  
> **username_0**: Does the problem remain NP-complete if diameters of $G$ and $H$ are fixed, say $diameter=2$ or a fixed $k$? Can one expect a Ramsey type theorem for diameter $2$ graphs $G$ where one asks "How large should a fixed $k$-diameter graph $d$-regular graph $H$ be for it to have a fixed $k$-diameter graph $G$ of vertex count $n_G$?"?  
> **username_0**: Again $G$ and $H$ are both regular.  
> **username_0**: I will post as new question.  
> **username_0**: It looks like diameter follows from your answer. not thinking correct today!  

---

