# Cayley subgraph isomorphism and complexity of linear subcode decision

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<n_2$, is deciding $C_1\cong D \subset C_2$ NP-complete? Note that code isomrphism is similar to graph isomorphism.

• Cayley graphs are edge-labeled. When you talk of homomorphisms from $G$ to $H$, do you mean that edge labels are ignored? – a3nm Oct 15 '13 at 16:30
• just ignore them or use them if they are useful. – T.... Oct 15 '13 at 17:04

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.
• 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. – T.... Oct 15 '13 at 18:59
• 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 Oct 15 '13 at 19:21
• 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$?"? – T.... Oct 15 '13 at 20:16
• Again $G$ and $H$ are both regular. – T.... Oct 15 '13 at 20:22