Re: NP - Hard -- Approximation algos

From: Foo Bar (foobar965_at_hotmail.com)
Date: 04/05/05


Date: 5 Apr 2005 10:55:31 -0700


"jumpstart" <jumpstart101@gmail.com> wrote in message news:<1112594935.719424.87720@f14g2000cwb.googlegroups.com>...

<snip>
>
> Regarding "This problem is known to be NP-hard."
> (In first page,2nd Column, 2nd Paragraph, 1st line)
>
> I would be happy to have answers based on my sub-questions.
>
> 1. What is NP- hard?

A NP-hard problem is a problem such that every problem in NP poly-time
reduces to it. A NP-complete problem is a problem in NP such that
every problem in NP poly-time (Karp-) reduces to it.

The distinction is important since NP is often defined as containing
only decision problems. For example, with this definition of NP,
Traveling Salesman is in NP, but phrased as "_Is_ there a route
shorter than k for this graph?" (NP-complete). The constructive
version (called Minimum Traveling Salesman), phrased as "Give me a
route shorter than k for this graph!", is NP-hard.

> 2. Why this problem is NP - hard?

Why? Because every problem in NP poly-time reduces to it. Why is
Traveling Salesman NP-complete? Same reason.

> 3. How to prove this is NP- hard?

Find a polynomial time reduction from a known NP-hard (or NP-complete)
problem to this problem.

You might try and look it up in Garey & Johnson (problem ND30). There
might be a reference to a proof there. If you are interested in
approximation algorithms, the other references are probably helpful.
Oh, and the problem is also called "Shortest Weight-Constrained Path".

What exactly is it you are interested in? The NP-hardness proof? A
FPTAS for the problem? Something else?

Also, be aware the some of the answers you have gotten from other
posters are partially incorrect...

/FB