# 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| > 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?

• In Problem 2, are you given s and t as well as G and SEQ? (The same point is ambiguous also in Problem 1, but it is NP-complete in both cases, so I do not care.) Feb 11 '11 at 20:31
• @Tsuyoshi yes s and t are part of the input (but I agree with you that it doesn't make any difference). I'm trying to find a reduction from an NPC problem, but there are no restrictions in the resulting path NODESEQ (nodes can be traversed more than once). Feb 11 '11 at 23:39
• (1) It is better to update the question accordingly. (2) I did not say that it does not make any difference in Problem 2. It may or may not, I do not know. Feb 11 '11 at 23:51
• I was talking about “Problem 1: Given G and SEQ …” and “Problem 2: Given G and SEQ …,” in case what I was talking about was not clear. Feb 11 '11 at 23:58
• I read revision 5 and I still do not get it. Are source and sink guaranteed to be unique? Feb 12 '11 at 0:10

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:

1. Start at $u_1$.
2. 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$.
3. Travel to $u_2$.
4. Visit each neighbor of $u_2$.
5. 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:

1. $f(x_0) = v_{source}$
2. $f(x_{n+1}) = v_{sink}$
3. $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$.

• I'm examining your answer. Just two notes: 1) it is not clear how to build P (is the sequence of nodes ininfluent)? 2) by construction it seems that SEQ has always a valid relaxed assignment (just follow the construction of P)? Feb 16 '11 at 21:14
• (1) Nice reduction! (2) Minor point: I think that the length of the path P (according to your construction) is O(n^2). (3) @Vor: Suppose that H is K_4, the complete graph on four vertices. How do you construct a valid relaxed node assignment from SEQ to G? Feb 16 '11 at 21:50
• @Tsuyoshi: Thanks. And you're right, it should be O(n^2). That's a typo.
– mhum
Feb 16 '11 at 22:02
• @Vor: SEQ has an assignment to $H$ (i.e.: we can assign $u_i$'s to $x_j$'s) but not necessarily to $G$ (i.e.: an assignment of $v_i$'s to $x_j$'s).
– mhum
Feb 17 '11 at 0:25
• @Vor: Also, I'm not sure what you mean by "ininfluent". The idea to building $P$ is that we want to build a path in $H$ that covers every edge in $H$. The construction I give is rather inefficient, but it produces a path that is still only polynomial length, so I don't really need to be more efficient.
– mhum
Feb 17 '11 at 0:56

EDIT: mjqxxxx points out in comments below that this construction can be slightly modified to obtain a poly-time algorithm for HAMILTONIAN-PATH. Thus, I think it's safe to say that this answer is incorrect as it stands. It looks like the error is in stating that $L_1 \cap L_2$ and $L_1 \cup L_2$ can be represented succinctly.

I think we can show that Problem 2 is tractable by showing the following: 1) the set of paths in G is a regular language, 2) the set of $NODESEQ$s has a compact description as a regular language. Problem 2 is thus reduced to checking if the intersection of two regular languages is non-empty.

Some preliminaries: Let $|V| = n$. Let $k$ be the length of $SEQ$. We will change terminology from the question a bit and define $NODESEQ$ to be the set of all strings of length $k$ over $V$ that result from a relaxed node assignment (both valid and invalid).

Let $P$ be the set of paths (both simple and non-simple) in $G$ beginning at the source node and ending at the sink node. Considering $P$ to be a set of strings over $V$, it should be evident that $P$ is a regular language accepted by a finite automaton (FA) with $O(n)$ states.

Next, we define the following: given a sequence of variables $SEQ$, let $NODESEQ(x_i = v_j)$ be the set of strings over $V$ obtained by substituting $v_j \in V$ for the variable $x_i$ in $SEQ$ and allowing all other variables to be free. For example, if $SEQ = (x_1,x_2,x_3,x_4,x_2,x_3,x_5)$, $NODESEQ(x_2 = v_3)$ can be represented by the regular expression "$. v_{3} . . v_{3} . .$" (the dots represent any element of $V$).

Now, we make two crucial observations: 1) Each $NODESEQ(x_i = v_j)$ can be recognized by an FA with $O(k)$ states and 2) $NODESEQ = \cap_{i=1}^m \cup_{j=1}^n NODESEQ(x_i = v_j)$.

Recall that if $L_1$ and $L_2$ are regular languages recognized by FAs with $n_1$ and $n_2$ states, respectively, then $L_1 \cup L_2$ and $L_1 \cap L_2$ can be recognized by an FA with $O(n_1 + n_2)$ states.

Thus, we conclude that $NODESEQ$ can be recognized by an FA with $O(kmn)$ states.

Finally, we note that a valid relaxed node assignment exists if and only if $P \cap NODESEQ$ is non-empty. Since we can build an FA for $P \cap NODESEQ$ with $O(kmn) + O(n) = O(kmn)$ states, I would call this problem tractable.

I would also note that the source and sink don't appear to play a material role in this problem. The construction of $P$ as a regular language is pretty much the same without enforcing the source/sink constraint.

• This same type of argument can be used to show (incorrectly) that HAMILTONIAN-PATH is tractable. In that case consider the intersection over $i$ of the union over $j$ of "$...v_i....$", where $v_i$ appears in the $j$th position (of $n$ total). The union over $j$ represents the set of strings of length $n$ in which $v_i$ appears. The intersection over $i$ of that represents the set of strings of length $n$ in which each $v_i$ appears. Finally, the intersection of that language with the language of all paths through $G$ is the set of Hamiltonian paths through $G$. Feb 14 '11 at 20:48
• Since all the $v_i$ need to be distinct for HAMILTONIAN-PATH, we can't simply take the intersection. In the asker's question, we allow non-simple paths.
– mhum
Feb 14 '11 at 20:53
• @mhum: Requiring each node to appear somewhere in a path of length $n$, where $n$ is the number of nodes in the graph, makes it impossible for any node to appear twice. (Note that in my example the intersection is over the index of $v_i$ and the union is over its position in the string... in yours it is the opposite.) Feb 14 '11 at 21:05
• Ah. I misunderstood your construction. In that case, I fear my answer is no good but I can't quite pin down exactly which step fails -- most likely in the union/intersection argument.
– mhum
Feb 14 '11 at 21:22
• @mhum: That's right; your statement that $L_1 \cup L_2$ and $L_1 \cap L_2$ can be recognized using $O(n_1 + n_2)$ states is not correct for DFAs. The etiquette is discussed a little on the meta site... leaving an incorrect answer up with a note seems to be the preference. Feb 14 '11 at 21:25