5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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, 2013 at 16:30
  • $\begingroup$ just ignore them or use them if they are useful. $\endgroup$
    – Turbo
    Oct 15, 2013 at 17:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\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$
    – Turbo
    Oct 15, 2013 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$
    – Joshua Grochow
    Oct 15, 2013 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$
    – Turbo
    Oct 15, 2013 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$
    – Turbo
    Oct 15, 2013 at 20:16
  • $\begingroup$ Again $G$ and $H$ are both regular. $\endgroup$
    – Turbo
    Oct 15, 2013 at 20:22

Your Answer

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

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