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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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