# Proving NP completeness of maximal length path

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 ﬁnding 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.

• Can you be more precise about what a "positive" or a "negative" neighbor is? – Panzerkroete Jun 12 '19 at 3:59
• It is just a partition (or labeling) in order to satisfy the given constraint where each internal node has two different labeled nodes before and after in the path. – Bassem Jun 12 '19 at 13:23
• I am still confused. 1. you say, you have a "network". What do you mean by that? A network data structure (used in the maximum flow problem )or just a undirected weighted graph $G$ which should model a network ? 2. Why do you want to consider $N^+$ and $N^-$? Let $\pi=(v_0,v_1,...v_n)$ be a path. Then by definition each $v_i, 0<i<n$ has exactly one positive/negative neighbor ($v_{i-1}, v_{i+1}$). So why $N^+$ and $N^-$? 3: Can your graph further contain cyles and is your graph connected? – Panzerkroete Jun 13 '19 at 13:02
• For the first point, I mean an undirected weighted graph 𝐺 representing a network. For the second point, not necessarily since the partition of neighbors happens before we construct a path .. so for example if a node $i$ has only two neighbors which are both + and $N^{-}(i)$ is empty .. then this node cannot be on the longest path since it violates the constraint. – Bassem Jun 13 '19 at 13:32
• I have no information on whether the network contains cycles but let's assume it is connected. – Bassem Jun 13 '19 at 13:33

I think here is a pitfall due to inaccurate notation. Notation for me:

1. A trail is a sequence of distinct connected edges.
2. A path is a trail with distinct vertices.

In the problem instance $$MNPL$$ (maximum neighbor path length) the sets $$(G,N^+, N^-)$$ and the weight function $$c_e$$ are given as input(and hereby fixed). Since $$N$$ is partitioned, for two vertices $$u,v$$ either $$\{u,v\}\notin E$$ or $$u$$ is a positive neighbor of $$v$$ or vice-versa. Especially $$u$$ and $$v$$ cannot be a positive neighbor of each other by definition ($$N$$ would not be partitioned). Hence $$G$$ must be a directed graph. Now, for any path $$s \rightsquigarrow (u,v,w) \rightsquigarrow t$$(not way nor cycle nor walk!) the neighbor-condition is fullfilled.

Maybe this was the real challenge of this exercise?

So, claim: $$MNPL$$ is $$NP$$-complete.

Proof: $$MNPL \leq_p LPP$$ (longest path problem) Consider the reduction $$f$$. For $$(G,N^+,N^-,c_e)$$ construct $$G'=(V',E',c_e')$$ as the following:

1. $$c_e'$$ = $$c_e$$
2. $$V' = V$$
3. $$E' = \bigcup_{v \in N^+(u), u \in N} (u,v) \cup \bigcup_{u \in N^-(v), v \in N} (v,u)$$

Clear: $$f$$ is computable and runs in poly-time ($$O(|E|)$$). By construction and with the observations above $$f$$ will construct a digraph from $$N$$ and the neighbor sets.

So $$f$$ is a reduction and $$MNPL \in NP$$ is obvious using "guess and check". Since $$LPP$$ is strongly $$NP$$-complete, $$MNPL$$ is as well strongly $$NP$$-complete. This is no decision problem but a maximization problem.

• Your idea looks clear to me .. but to prove a problem is NP-complete aren't we supposed to reduce an NP-complete problem to our problem? – Bassem Jun 13 '19 at 19:34
• I do not provide a reduction here because I think, that problem is $NP$-complete because you restrictions on the neighbors are to strict. For example, given the complete graph $K_5$ (look here for its appearence)where all edges have weight one. Here, the longest path would be obvious contain all five vertices (no matter which vertix is $s$ or $t$). However for any $s-u-v-w-t$ path $N^+(v)=N^-(v)=\{s,u,w,t\} \neq \{u,w\}$. Hence your neighbor condition is not fulfilled. By that, I cannot reduce to the $HamiltonianPath$ -problem – Panzerkroete Jun 13 '19 at 22:38
• This is because a hamiltonian path in for example $G=K_5$ is not a valid longest path in your network graph $G'$. The standard polynomial reduction ($G'$ with $n$ vertices has longest path with length $n-1$ iff. $G$ has a hamiltonian path ) does not work here.The implication Hpath to longest path is not true. So, there is no reduction to any known $NP$-hard problem (at least I could not find one) and so $MNPL$ is not NP-complete. Either your definiton of neighbor is somehow wrong or the problem is really in $P$. Do you have this exercise somewhere and can link the source? – Panzerkroete Jun 13 '19 at 22:47
• I have no source for it .. it was provided by a professor as an exercise to prove NP completeness. I was thinking that either Hamiltonian path or TSP problems could be the problems to use for the proof and then I was thinking about constrained shortest path problem but I still couldn't find clear reduction proof. – Bassem Jun 14 '19 at 0:58
• @Bassem I added the core argument for reduction to the longest path problem for directed graphs. At a few points a bit more argumentation is needed (like why is the neighbor condition fulfilled by a directed graph, why is $f(w) \in LPP => w \in MNPL$?, why is $MNPL \in NP$?). Give me feedback if you have doubts – Panzerkroete Jun 14 '19 at 1:14