STAMM@DBNINF5.BITNET (Hermann Stamm) (10/04/90)
Results on NDSP
=================
I have asked for the complexity of the following problem:
-----------------------------------------------------------------------------
NEGATIVE-DIRECTED-SIMPLE-PATH (NDSP)
Instance: Digraph D=(V,A) with arc-weights w:A-->{-1,0,+1} ,
vertices s,t \in V .
Question: Exists a simple directed path from s leading to t with
negative total weight ?
Remarks: 1) Negative directed cycles in D are allowed !
2) The path need not to be the most negative one !
( Otherwise DHP \alpha NDSP )
3) If arc-weights are w:{-1,0,1,2,...,|V|}, then DHP \alpha NDSP !
( w(a):=|V|-2 iff a=(s,v) \in A and v \in V )
( w(a):=-1 otherwise )
-----------------------------------------------------------------------------
I have got 7 answers with 3 different NP-completeness reductions for the
above problem, the most simple one basing on remark 3:
Replace each arc with cost |V|-2 by a simple directed path of length
|V|-2 with |V|-3 new vertices and each arc having cost +1. This produces
a digraph satisfying the restrictions of NDSP and having a negative directed
simple path from s leading to t if and only if having a Hamiltonian Path
from s to t. Thus DHP \alpha NDSP.
Remark: The weight |V|-2 is wrong !
It has clearly to be |V|-3 !
Thanks for the interest and the given anwswers ,
Hermann Stamm
Universitaet Bonn
STAMM@DBNINF5.BITNET