[comp.theory] Complexity of the NEGATIVE-DIRECTED-SIMPLE-PATH problem

STAMM@DBNINF5.BITNET (Hermann Stamm) (09/27/90)

I am interested in the following problem, whose complexity I am not able
to determine ( is it in P or is it NP-hard ? ) :


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                             )


Thanks in advance ,

Hermann Stamm
Universitaet Bonn
STAMM@DBNINF5.BITNET