Xref: utzoo comp.theory:1687 sci.math:16002
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!zaphod.mps.ohio-state.edu!mips!cs.uoregon.edu!ogicse!uidaho!ted.cs.uidaho.edu!foster
From: foster@ted.cs.uidaho.edu
Newsgroups: comp.theory,sci.math
Subject: Re: Disjoint Paths Problem (A variation)
Message-ID: <1991Mar22.204636.15827@groucho>
Date: 22 Mar 91 20:46:36 GMT
References: <1991Mar20.170612.13200@garfield.cs.mun.ca>
Sender: @groucho
Organization: University of Idaho
Lines: 9
Nntp-Posting-Host: ted.cs.uidaho.edu

In article <1991Mar20.170612.13200@garfield.cs.mun.ca> grant@garfield.cs.mun.ca (Grant Burton) writes:
>
>Questions:
>2) DCP is known to be NP-complete, and it is a subproblem of IDCP, 
>   therefore IDCP must also NP-complete, do you agree ?

No.  2-sat is a subproblem of 3-sat, yet is not np-complete.

James