1
$\begingroup$

Input: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given.

Output: Is it possible to order the incident edges set of each vertex and choose a starting vertex $s \in V$ so that a pre-order DFS traversal starting from $s$ prints out a sequence of labels of visited vertices which matches the given sequence.

Any idea on this problem? It is solvable on trees by Dynamic Programming. But for general graph, it seems to be much harder.

$\endgroup$
1
  • 1
    $\begingroup$ DP when given graph is a tree: Do the following for every vertex v: Set it as the root of the tree, going bottom-up and consider the subproblem (v, i, j) which gives the answer to the question "Does the subtree rooted at v orientable to have the pre-order traversal matching subsequence from index i to index j"? $\endgroup$ Jul 14, 2018 at 10:01

1 Answer 1

0
$\begingroup$

We reduce from Hamiltonian cycle. Given a graph $G$, we construct new labelled graph as follows:

  • Label each vertex of $G$ by $\mathrm{A}$
  • To each vertex of $G$ connect it with a hanging vertex "above" it and label this vertex by $\mathrm{F}$
  • For each edge $e$ of $G$, add a "middle" vertex labelled by $\mathrm{K}$, and connect each "middle" vertex to the two $\mathrm{F}$ vertices above the two $\mathrm{A}$ end points of its corresponding edge.

The sequence will be $\mathrm{AFKAFK}\dots\mathrm{AFK}$$KKK..\dots KKK$ where we repeat the pattern $\mathrm{AFK}$ the number of times equal to the number of vertices of $G$, i.e. $|V(G)|$. And the number of trailing $\mathrm{K}$ (written in italic for clarity) equals $|E(G)|-|V(G)|$, i.e. after finishing the Hamiltonian cycle, the traversal needs to come back and collect the remaining "middle" vertices.

If $G$ is Hamiltonian, clearly we can order the neighborhood of each vertex so that the edge that will be taken at each vertex is in accordance with the Hamiltonian cycle.

Conversely, if we can order the neighborhood of each vertex and choosing a string vertex so that the preorder traversal prints out the required sequence then we can follow the path delineated by the traversal to figure out the Hamiltonian cycle. Indeed, if at some point you get stuck, then there would be the very FIRST time you get stuck somewhere. But clearly, if so, you need to produce a $\mathrm{KK}$ before the trailing "garbage" sequence begins. In short, you cannot get way back and branch (at least for the FIRST time) without printing out a $\mathrm{KK}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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