0
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Can you be more precise about what a "positive" or a "negative" neighbor is? $\endgroup$ – Panzerkroete Jun 12 '19 at 3:59
  • $\begingroup$ 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. $\endgroup$ – Bassem Jun 12 '19 at 13:23
  • $\begingroup$ 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? $\endgroup$ – Panzerkroete Jun 13 '19 at 13:02
  • $\begingroup$ 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. $\endgroup$ – Bassem Jun 13 '19 at 13:32
  • $\begingroup$ I have no information on whether the network contains cycles but let's assume it is connected. $\endgroup$ – Bassem Jun 13 '19 at 13:33
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Bassem Jun 13 '19 at 19:34
  • $\begingroup$ 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 $\endgroup$ – Panzerkroete Jun 13 '19 at 22:38
  • $\begingroup$ 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? $\endgroup$ – Panzerkroete Jun 13 '19 at 22:47
  • $\begingroup$ 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. $\endgroup$ – Bassem Jun 14 '19 at 0:58
  • $\begingroup$ @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 $\endgroup$ – Panzerkroete Jun 14 '19 at 1:14

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.