Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!decwrl!ucbvax!DBNINF5.BITNET!STAMM
From: STAMM@DBNINF5.BITNET (Hermann Stamm)
Newsgroups: comp.theory
Subject: Result:  NDSP is NP-complete.
Message-ID: <9010032018.AA03838@irt.watson.ibm.com>
Date: 3 Oct 90 20:18:49 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Hermann Stamm <STAMM%DBNINF5.BITNET@VM1.NoDak.EDU>
Lines: 44


 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