<p>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.</p>

<p>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:</p>

<ol>
<li>Start at $u_1$.</li>
<li>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$.</li>
<li>Travel to $u_2$.</li>
<li>Visit each neighbor of $u_2$.</li>
<li>etc...</li>
</ol>

<p>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)$.</p>

<p>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.</p>

<p>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$. </p>

<p>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:</p>

<ol>
<li>$f(x_0) = v_{source}$</li>
<li>$f(x_{n+1}) = v_{sink}$</li>
<li>$f(x_i) = v_{c(u_i)}$</li>
</ol>

<p>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$.</p>

CC BY-SA 2.5
2011-02-16T21:14:14.323Z
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)?
Marzio De Biasi
CC BY-SA 2.5
2011-02-16T21:50:47.967Z
(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?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-16T22:02:59.940Z
@Tsuyoshi: Thanks. And you're right, it should be O(n^2). That's a typo.
mhum
CC BY-SA 2.5
2011-02-17T00:25:15.713Z
@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
CC BY-SA 2.5
2011-02-17T00:56:48.027Z
@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
CC BY-SA 2.5
2011-02-17T07:47:50.807Z
@mhum: Yesterday I read your answer superficially, now I see that it is correct and is a great reduction !!! It seems incredible (to me) that a simple node assignment on a 3 vertices complete graph can capture the whole NP class! Is the 3 vertices graph trick used in other reductions (I'm not an expert)?
Marzio De Biasi
CC BY-SA 2.5
2011-02-17T14:48:12.170Z
@Vor: The main thing to know is the fact that you have a graph homomorphism $f:G \rightarrow H$ (i.e.: if $(u,v)$ is an edge in $G$, then $(f(u), f(v))$ is an edge in $H$) where $H$ is a clique of size $k$ if and only if you have a $k$-coloring of $G$. More simply, the node assignment on 3 vertices is the same as 3-coloring.
mhum
CC BY-SA 2.5
2011-02-16T17:58:23.947Z
2011-02-16T22:03:32.153Z
2011-02-16T22:03:32.153Z
mhum
<p>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.</p>

<hr>

<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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$). </p>

<p>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)$. </p>

<p>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. </p>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-02-14T20:48:34.223Z
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$.
mjqxxxx
CC BY-SA 2.5
2011-02-14T20:53:55.377Z
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
CC BY-SA 2.5
2011-02-14T21:05:09.233Z
@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.)
mjqxxxx
CC BY-SA 2.5
2011-02-14T21:22:29.613Z
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
CC BY-SA 2.5
2011-02-14T21:25:54.027Z
@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.
mjqxxxx
CC BY-SA 2.5
2011-02-14T21:36:30.223Z
That's probably it. You can do it for NFAs but maybe not for DFAs without super-polynomial blowup? I guess in this case we need to be very careful about conversions.
mhum
CC BY-SA 2.5
2011-02-15T22:28:03.030Z
The NFA size of the intersection L1∩L2 can also be the product of the NFA sizes of L1 and of L2.  For example, let p and q be distinct primes and let L1 (resp. L2) be the language consisting of the strings whose length is divisible by p (resp. q).  L1 and L2 even have a DFA of size p and q, respectively, but any NFA for L1∩L2 requires size pq.  Note that a language and its complement have different NFA sizes in general.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-16T18:28:29.647Z
Huh. It looks like I botched this one up real good. :) For some reason, I thought you could just flip the accepting states in an NFA to get the complement, but I guess that's not the case.
mhum
CC BY-SA 2.5
2011-02-14T20:21:23.377Z
2011-02-16T18:29:16.790Z
2011-02-16T18:29:16.790Z
mhum
<p>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).</p>

<p>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]$</p>

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

<p>A <strong>node assignment</strong> 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.</p>

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

<p>For example: $NODESEQ = (s,v_1,v_7,v_9,v_1,v_7,t)$</p>

<p>A <strong>valid node assignment</strong> 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$.</p>

<p><strong>Problem 1:</strong></p>

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

<p>I'm not an expert, but if we take $m=n=|V|$ and $SEQ=(x_1,...,x_n)$ then the problem becomes the <em>Hamiltonian Path</em> 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).</p>

<p>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 <strong>relaxed node assignment</strong>). We get an (apparently) simpler problem.</p>

<p><strong>Problem 2:</strong></p>

<blockquote>
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.
</blockquote>

<p>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.</p>

<p>Is this problem known?</p>

<p>Is it still an NPC problem?</p>

CC BY-SA 2.5
2011-02-11T20:31:28.020Z
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.)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-11T23:39:28.903Z
@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).
Marzio De Biasi
CC BY-SA 2.5
2011-02-11T23:51:22.903Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-11T23:58:57.577Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T00:10:01.247Z
I read revision 5 and I still do not get it.  Are source and sink guaranteed to be unique?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T00:14:46.147Z
@Tsuyoshi ok, I modified the question ... check if it is clear enough, (and tell me how can I make it better).
Marzio De Biasi
CC BY-SA 2.5
2011-02-12T00:22:34.310Z
Let me repeat my last comment in other words. You write “Given a directed graph G with a source and a sink and a sequence of variables SEQ …,” but this text is ambiguous. For example, suppose that G has more than one source. There are two interpretations here: (a) An algorithm is specified which source to treat as s; in other words, s is given as part of input. (b) An algorithm is free to choose any source as s; in other words, s is not given as part of input. Which is your intent? The same applies to the case where G has more than one sink.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T00:24:56.460Z
(cont’d)  Sorry to be picky, but I just wanted to make it clear what I was asking.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T00:30:41.323Z
I realized that this ambiguity (whether s and t are specified or not) is only a formal concern and irrelevant to the complexity of the problem (if I am not mistaken).  Sorry for the noise.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T13:51:38.960Z
@Tsuyoshi: It wasn't *necessarily* irrelevant.  If the case where $s$ and $t$ are unspecified is NP-complete, then so is the case where they are specified; the converse isn't obvious (is it?).  But I suspect that the former case is NP-complete.
mjqxxxx
CC BY-SA 2.5
2011-02-12T17:18:22.543Z
@mjqxxxx: The converse (a reduction from the “specified” case to the “unspecified” case) is as follows.  Let G, s and t be given.  The key fact is that if G has sources other than s and sinks other than t, then they cannot be used.  Therefore we can remove them from G until s is the unique source and t is the unique sink, and apply the algorithm for the “unspecified” case.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T17:50:14.193Z
I think this can be solved using the following two observations: 1) the set of paths is a regular language, 2) the set of NODESEQs is a CFL with succinct description. The intersection of a regular language and a CFL is a CFL, so we can easily test for emptiness.
mhum
CC BY-SA 2.5
2011-02-12T18:02:24.863Z
@mhum: I fail to see how the (finite but exponential-size) set of NODESEQs has a poly-size context-free grammar.  We need the condition that the first letter and the fourth letter are the same, and so on.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-12T23:31:30.017Z
@Tsuyoshi: I think you're right. I was overly optimistic about turning NODESEQ into a CFL. Oh well. Back to the drawing board.
mhum
<ds.algorithms><graph-algorithms>
Is it easy to "fit a wrapped chain in a graph"?
Marzio De Biasi
# Is it easy to "fit a wrapped chain in a graph"?

(Asked by: username_0 on 2011-02-11)

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?

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: 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.)  
> **username_0**: @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).  
> **username_1**: (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.  
> **username_1**: 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.  
> **username_1**: I read revision 5 and I still do not get it.  Are source and sink guaranteed to be unique?  
> **username_0**: @Tsuyoshi ok, I modified the question ... check if it is clear enough, (and tell me how can I make it better).  
> **username_1**: Let me repeat my last comment in other words. You write “Given a directed graph G with a source and a sink and a sequence of variables SEQ …,” but this text is ambiguous. For example, suppose that G has more than one source. There are two interpretations here: (a) An algorithm is specified which source to treat as s; in other words, s is given as part of input. (b) An algorithm is free to choose any source as s; in other words, s is not given as part of input. Which is your intent? The same applies to the case where G has more than one sink.  (more)  
> **username_1**: (cont’d)  Sorry to be picky, but I just wanted to make it clear what I was asking.  
> **username_1**: I realized that this ambiguity (whether s and t are specified or not) is only a formal concern and irrelevant to the complexity of the problem (if I am not mistaken).  Sorry for the noise.  
> **username_2**: @Tsuyoshi: It wasn't *necessarily* irrelevant.  If the case where $s$ and $t$ are unspecified is NP-complete, then so is the case where they are specified; the converse isn't obvious (is it?).  But I suspect that the former case is NP-complete.  
> **username_1**: @username_2: The converse (a reduction from the “specified” case to the “unspecified” case) is as follows.  Let G, s and t be given.  The key fact is that if G has sources other than s and sinks other than t, then they cannot be used.  Therefore we can remove them from G until s is the unique source and t is the unique sink, and apply the algorithm for the “unspecified” case.  
> **username_3**: I think this can be solved using the following two observations: 1) the set of paths is a regular language, 2) the set of NODESEQs is a CFL with succinct description. The intersection of a regular language and a CFL is a CFL, so we can easily test for emptiness.  
> **username_1**: @username_3: I fail to see how the (finite but exponential-size) set of NODESEQs has a poly-size context-free grammar.  We need the condition that the first letter and the fourth letter are the same, and so on.  
> **username_3**: @Tsuyoshi: I think you're right. I was overly optimistic about turning NODESEQ into a CFL. Oh well. Back to the drawing board.  

---

## 2 answers

### Answer by username_3 on 2011-02-16. Score: 4 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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)?  
> **username_1**: (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?  
> **username_3**: @Tsuyoshi: Thanks. And you're right, it should be O(n^2). That's a typo.  
> **username_3**: @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).  
> **username_3**: @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.  
> **username_0**: @username_3: Yesterday I read your answer superficially, now I see that it is correct and is a great reduction !!! It seems incredible (to me) that a simple node assignment on a 3 vertices complete graph can capture the whole NP class! Is the 3 vertices graph trick used in other reductions (I'm not an expert)?  
> **username_3**: @Vor: The main thing to know is the fact that you have a graph homomorphism $f:G \rightarrow H$ (i.e.: if $(u,v)$ is an edge in $G$, then $(f(u), f(v))$ is an edge in $H$) where $H$ is a clique of size $k$ if and only if you have a $k$-coloring of $G$. More simply, the node assignment on 3 vertices is the same as 3-coloring.  

---

### Answer by username_3 on 2011-02-14. Score: 0

EDIT: username_2 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.

> **Comments:**
> **username_2**: 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$.  
> **username_3**: 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.  
> **username_2**: @username_3: 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.)  
> **username_3**: 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.  
> **username_2**: @username_3: 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.  
> **username_3**: That's probably it. You can do it for NFAs but maybe not for DFAs without super-polynomial blowup? I guess in this case we need to be very careful about conversions.  
> **username_1**: The NFA size of the intersection L1∩L2 can also be the product of the NFA sizes of L1 and of L2.  For example, let p and q be distinct primes and let L1 (resp. L2) be the language consisting of the strings whose length is divisible by p (resp. q).  L1 and L2 even have a DFA of size p and q, respectively, but any NFA for L1∩L2 requires size pq.  Note that a language and its complement have different NFA sizes in general.  
> **username_3**: Huh. It looks like I botched this one up real good. :) For some reason, I thought you could just flip the accepting states in an NFA to get the complement, but I guess that's not the case.  

---

