7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Tsuyoshi Ito Feb 11 '11 at 20:31
  • $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Feb 11 '11 at 23:39
  • $\begingroup$ (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. $\endgroup$ – Tsuyoshi Ito Feb 11 '11 at 23:51
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Feb 11 '11 at 23:58
  • $\begingroup$ I read revision 5 and I still do not get it. Are source and sink guaranteed to be unique? $\endgroup$ – Tsuyoshi Ito Feb 12 '11 at 0:10
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Marzio De Biasi Feb 16 '11 at 21:14
  • $\begingroup$ (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? $\endgroup$ – Tsuyoshi Ito Feb 16 '11 at 21:50
  • $\begingroup$ @Tsuyoshi: Thanks. And you're right, it should be O(n^2). That's a typo. $\endgroup$ – mhum Feb 16 '11 at 22:02
  • $\begingroup$ @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). $\endgroup$ – mhum Feb 17 '11 at 0:25
  • $\begingroup$ @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. $\endgroup$ – mhum Feb 17 '11 at 0:56
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – mjqxxxx Feb 14 '11 at 20:48
  • $\begingroup$ 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. $\endgroup$ – mhum Feb 14 '11 at 20:53
  • $\begingroup$ @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.) $\endgroup$ – mjqxxxx Feb 14 '11 at 21:05
  • $\begingroup$ 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. $\endgroup$ – mhum Feb 14 '11 at 21:22
  • $\begingroup$ @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. $\endgroup$ – mjqxxxx Feb 14 '11 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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