Is it easy to "fit a wrapped chain in a graph"? Given a directed graph $G=(V,A)$ with a unique source node $s$ (a node without incoming edges) and a unique sink node $t$ (a node without outgoing edges).

Given a sequence of variables $SEQ = (x_{i_1},x_{i_2},...,x_{i_m})$ with $|SEQ| &gt; 2$ and each $i_j \in [1..m]$

For example $SEQ = (x_1,x_2,x_3,x_4,x_2,x_3,x_5)$ (m=5).

A node assignment is a function $f: \{x_1,...,x_m\} \rightarrow V$ such that if $i \neq j$ then $f(x_i) \neq f(x_j)$ (it maps each $x_j$ to a different node of the graph). Now, if in $SEQ$ we substitute $x_j$ with $f(x_j)$ we obtain a sequence $NODESEQ$ of nodes.

We want to start from $s$ and end in $t$ so trivially $x_1 = s, x_m = t$.

For example: $NODESEQ = (s,v_1,v_7,v_9,v_1,v_7,t)$

A valid node assignment is an assignment such that if we substitute each $x_{i_j}$ with $f(x_{i_j})$ in the sequence $SEQ$ we obtain a valid path from $s$ to $t$.

Problem 1:


Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid node assignment exists.


I'm not an expert, but if we take $m=n=|V|$ and $SEQ=(x_1,...,x_n)$ then the problem becomes the Hamiltonian Path problem. Informally HAM-PATH can be reduced to Problem 1, adding a source node $s$ and a sink node $t$, two extra variables at the beginning and end of $SEQ$: $(x_s,x_1,...,x_n,x_t)$ and edges $(s,u), (v,t)$ for every $u,v \in V$, (hence Problem 1 is in NPC).

But we can modify it and drop the condition that if $i \neq j$ then $f(x_i) \neq f(x_j)$ i.e we can assign the same node $v$ to more than one $x_i$ (I call it relaxed node assignment). We get an (apparently) simpler problem.

Problem 2:


Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid **relaxed node assignment** exists.


An informal way to describe the problem: we have a chain made of segments. Now we wrap it up in some casual order and join some innermost endpoints. The problem 2 consists in checking if such wrapped chain can "fit" in a given graph.

Is this problem known?

Is it still an NPC problem?
Allow me to try to redeem my previous incorrect answer with an attempt at showing that this problem is NP-complete via a reduction from GRAPH 3-COLORABILITY. The key idea is to identify SEQ as a list of edges of some graph and observe that a "relaxed node assignment" corresponds to a graph homomorphism.

Let $H = (U, E)$ be a connected, undirected graph with $U = \{u_1, u_2, \ldots, u_n\}$. Let $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ be a (non-simple) path in $H$ that traverses every edge at least once (i.e.: if there is an edge between $u_i$ and $u_j$, then they appear consecutively in $P$ in either order). First, we need to show that $P$ is not too long. We can construct $P$ as follows:


Start at $u_1$.
Visit each neighbor of $u_1$, returning to $u_1$ after each visit. I.e., if the neighbors of $u_1$ are $u_{n_1}, u_{n_2}, \ldots, u_{n_d}$, we have the following sequence: $u_1, u_{n_1}, u_1, u_{n_2}, u_1, \dots, u_1, u_{n_d}, u_1$.
Travel to $u_2$.
Visit each neighbor of $u_2$.
etc...


By visiting each vertex's neighbors, each edge in $H$ is traversed. Each neighbor visitation step adds $O(n)$ steps to the path. Each travel to a successive vertex adds another $O(n)$ steps. So, in total length of $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ is $O(n^2)$.

Let $SEQ = (x_0, x_{a_1}, x_{a_2}, x_{a_3},\ldots,x_{a_p}, x_{n+1})$ be the sequence of variables.

Let $G = (V, A)$ be the complete, directed graph on three vertices adjoined with a universal source and a universal sink. Explicitly, let $V = \{v_1, v_2, v_3, v_{source}, v_{sink}\}$. There is an arc from $v_{source}$ to $v_i$ and from $v_i$ to $v_{sink}$ for $i=1,2,3$. And, for all $i,j = 1,2,3, i \neq j$ there is an arc from $v_i$ to $v_j$. 

Finally, we claim that a valid relaxed node assignment from $SEQ$ to $G$ exists iff $H$ is 3-colorable. Let $c:U \rightarrow \{1,2,3\}$ be a 3-coloring of $H$. Let $f:X \rightarrow V$ be defined by:


$f(x_0) = v_{source}$
$f(x_{n+1}) = v_{sink}$
$f(x_i) = v_{c(u_i)}$


It should be clear that $f$ is a valid relaxed node assignment. It should be equally clear that we can reverse this construction to use any valid relaxed node assignment to define a 3-coloring of $H$.