2
$\begingroup$

Say I am giving a directed edge-colored graph $G^c(V,E)$. Every vertex has the same out-degree. Every vertex has exactly one edge of one color in $I_c$. So for example, if you have a set of color $I_c = \{R,G,B\}$, then every vertex has one R-edge, one G-edge and one B-edge.

I'm looking for a sequence of color(if any) such that, if you start from any vertex and follow this sequence, you will always end up at the same vertex. For example, if say R-G is an answer, and $v_0$ is the end vertex. Then for every vertex $v\in V(G)$, you can start at v, walk on Red edge, and then Green edge, and then you will arrive at $v_0$.

I was thinking of finding a spanning tree with properly colored edges. But that didn't work out. Can anyone please point me a direction? I am not looking for an exact answer.

My own observations: 1. If we reverse the direction of all edges. Then the end node $v_0$ is a node such that, for every edges $v_i\in V(G)$, there exist a path $p_i$ that connects $v_0$ and $v_i$. Moreover, all $p_i$ has same sequence of color. 2. If we take a look at the vertex connecting to the end node $v_0$. Let the set of nodes being $n_1$. Then for all $v\in n_1$, either v connects to another $v'\in n_1$, or $v'$ connect to itself with a minus-one sequence( the sequence without last element).

** Notice that color can be repeated in the sequence.

Edit 1. 1. I forget to mention in the problem. I am finding an algorithm that can help me find a sequence(if any).

Edit 2. Thanks for the reply. Based on the reply, I have a maybe simpler implementation for algorithm checking whether there is a sync word or not. Given the states(nodes) and the transition(edges), you traverse through each 2-combination of states(nodes). That is : $(s_0,s_1), (s_1, s_2)$, ..., etc. This can be easily done with double for-loop and the complexity here is $O(n^2)$.

Then for each pair, we use a bfs to see if we can get to the same state. The neighbors of each node in bfs is the pair of nodes you get by moving each node one step. For example, if you havea transition $\delta$, and a pair of states $(s_1, s_2)$. You move to $(\delta(s_1), \delta(s_2))$. If the transition of two states are the same, you find the answer. Otherwise, put the neighbor in queue and keep doing bfs.

One can utilize hash_set to make the algorithm faster.

Therefore

$\endgroup$
2
$\begingroup$

Edit #2. Here's a (naive but polynomial-time) algorithm:

Observe that there's a synchronizing sequence for all the nodes in the graph if and only if there's a synchronizing sequence for each pair of nodes in the graph. (Indeed, synchronizing all nodes synchronizes each pair; and if you can synchronize each pair, then you can synchronize all of the nodes as follows: until all nodes are synchronized, find two nodes that aren't and read off their synchronizing sequence. Now there are fewer unsynchronized nodes.)

So it suffices to search for a synchronizing sequence for each pair of nodes separately. To do so, first we collect information on how much we can synchronize in a single step. Consider each pair of nodes and each color of edge, and determine where you will end up if you start on those two nodes and follow that colored edge. (Either the two nodes will converge, or they'll end up on two distinct nodes.)

You can record this transition information in a new graph: Let the new graph have one node for each unordered pair of nodes $\{a,b\}$ in the old graph (including when $a=b$, so the new node is just $\{a,a\}$). (There are $\frac{1}{2}N(N+1)$ total nodes). There's a $w$-colored edge from $\{a,b\}$ to $\{c,d\}$ if by starting on $a$ and $b$ and following the $w$-colored edges, you end up at $c$ and $d$ (order doesn't matter).

Now, you can use ordinary path-finding techniques on this new graph (like breadth-first search) to see if for each starting pair of states, it's possible to find a color sequence that will synchronize them. Your search is bounded because of course the path must not be longer than the number of nodes in the graph.


Original response. I'm not sure if you're trying to prove that this is always possible, or trying to come up with an algorithm that will find such a node/color-sequence if one exists, or something else.

But here's a quick (maybe too trivial?) example that sometimes there won't be any such sequence: consider a two-node graph where each node points at the other. We'll use one color to color the edges, and observe that no color sequence will converge onto a single node.

Edit #1: This problem seems to be equivalent to the problem of finding a synchronizing word for a deterministic finite automaton (https://en.wikipedia.org/wiki/Synchronizing_word), in which case according to that Wikipedia page, there exists a polynomial-time algorithm for discovering if such a word exists. It's unclear to me at first glance if we know of an efficient algorithm for actually finding such a word. I've defined a polynomial-time algorithm above.

$\endgroup$
  • $\begingroup$ Thanks for your reply! I know that there might not be such sequence. So I'm designing an algorithm to find one if it exists. $\endgroup$ – Steve Lee Jul 18 '16 at 3:37
  • $\begingroup$ @Joffan, Yes, but I believe the aim isn't to send every node in a cycle that returns to the start, but rather to send every node to converge onto a single node via a single color sequence. $\endgroup$ – user326210 Jul 18 '16 at 3:39
  • $\begingroup$ Wow this is really cool! I'll read it over! $\endgroup$ – Steve Lee Jul 18 '16 at 3:44

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.