Path: utzoo!attcan!uunet!snorkelwacker!usc!ucsd!ucbvax!DBNINF5.BITNET!STAMM
From: STAMM@DBNINF5.BITNET (Hermann Stamm)
Newsgroups: comp.theory
Subject: Complexity of the NEGATIVE-DIRECTED-SIMPLE-PATH problem
Message-ID: <9009261736.AA27279@irt.watson.ibm.com>
Date: 26 Sep 90 17:36:52 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Hermann Stamm <STAMM%DBNINF5.BITNET@VM1.NoDak.EDU>
Lines: 29

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