This
paper shows that WHP is NP-hard by reducing the HP
problem to a WHP problem. It is known that the HP problem
is NP-complete (Garey and Johnson, 1979; Papadimitriou, 1995;
and Gormen et al., 2001). First, it is proved that
WHP belongs to NP. Given an instance of the problem,
the sequence of n = |V| distinct vertices in the path
is used as a certificate. The verification algorithm checks
that this sequence contains each vertex exactly once, sums
up the edge weights, and checks whether the sum is at most
K. This algorithm can certainly be performed in polynomial
time. Therefore, WHP Î NP.
To
prove that WHP is NP-hard, it is showed that HP
µ WHP. Let G = (V, E) be an instance
of HP. An instance of the WHP is constructed
as follows. A complete graph G'= (V, E) is computed,
where E'= {{vi, vj}
| vi, vj, Î V}, and
the nonnegative integer Z0+ on
the edges is defined by Z0+ =
k or less, if {vi, vj}
Î E; otherwise more than k, if {vi,
vj} Ï E. The instance of WHP
is then (G', K), which is easily formed in polynomial
time. The construction is depicted in Figure 1. Thus, if a
set of nonnegative integer weights are assigned to the edges
of an undirected graph, then the computation of a minimum
weighted Hamiltonian path remains NP-hard. |
