Subgraph Isomorphism Relaxation I want to find a more relaxed subgraph isomorphism. Specifically I want to find a subset of vertices in one graph, G, connected by a non-overlapping set of walks, that correspond to another set of vertices in another graph H, connected by edges. In other words, instead of a set of edges in the subgraph I want a set of non-overlapping walks/paths.
More formally (this might be lacking precision),
Let $G=(V,E)$ and $H=(V',E')$; is there a subgraph $G_0(V_0,E_0)$ where $V_0 \subseteq V$, $E_0 \subseteq E \bigcap (V_0 \times V_0)$ and $W_0 \subseteq \{(v_i....v_j) | \{v_k,v_{k+1}\}\in E_0\}$, s.t. $\exists f:V_0\rightarrow V'$ and $w_{ij}\in W_0 \iff \{f(v_i),f(v_j)\} \in E'$ and $\forall \{v_k, v_{k+1}\}\in w_{ij} \not\in w_{i'j'} \forall i\ne i'\bigcap j\ne j'$
I have a feeling that this problem is NP-Hard or like standard graph isomorphism does not have a poly-time algorithm identified yet. Any help though, in pointing me in the right direction would be much appreciated.
 A: Just like subgraph isomorphism, this is NP-hard because you can reduce the Hamiltonian cycle problem to it: if $H$ is an $n$-vertex cycle and $G$ is any graph on $n$ vertices, the only way to find a subdivision of $H$ inside $G$ is to find a copy of $H$ inside $G$, and a copy of $H$ inside $G$ is a Hamiltonian cycle.
It becomes easier if $H$ is a fixed graph and only $G$ is given as input. According to a paper of Robertson and Seymour, for any fixed $k$, if we specify $k$ pairs of vertices $(s_1, t_1), \dots, (s_k,t_k)$ in an $n$-vertex graph $G$, we can try to find pairwise vertex-disjoint paths between each pair of vertices in $O(n^3)$ time. 
This lets us test if a subdivision of $H$ exists inside $G$, with the vertices of $H$ having fixed locations in $G$, as follows. For each vertex $v$ of $H$, clone the corresponding vertex of $G$ a total of $\deg_H(v)$ times. Then, for each edge of $H$, pick a copy of each endpoint and take those to be a pair $(s_i,t_i)$, and apply the Robertson-Seymour algorithm.
Finally, this lets us test if any subdivision $H$ exists inside $G$, in $O(n^{3+|V(H)|})$ time. Just test all the possible locations of the vertices of $H$.
