I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the length of edge $e \in E$. For each node $i \in N$, suppose the set $N(i)$ is partitioned into two subsets, $N^+(i)$ and $N^-(i)$ such that $j \in N^+(i)(j \in N^-(i))$ is referred to as a positive (negative) neighbor of $i$. (Note: Regardless of whether $j$ is a positive or negative neighbor of $i$, $i$ can be either a positive or negative neighbor of j.) Consider the problem of finding a maximum-length path $(s =) i(0)–i(1)–···–i(h)(= t)$ in $G$ between two nodes $s ∈ N$ and $t ∈ N$ subject to the following restriction: For each internal node $i(k)(k \in\{1,...,h − 1\})$ on the path, the set $\{i(k − 1),i(k + 1)\}$ must contain exactly one positive neighbor and one negative neighbor of $i(k)$. Prove NP-completeness of the decision problem and state whether it strongly NP-complete or not.
I wonder about the steps of the proof and whether shall I start from the longest path problem or from another problem instance.