It is widely believed that showing a problem to be
NP-complete is tantamount to proving its computational intractability. In this
paper we show that a number of NP-complete problems remain NP-complete even
when their domains are substantially restricted. First we show the completeness
of Simple Max Cut (Max Cut with edge weights restricted to value 1), and, as a
corollary, the completeness of the Optimal Linear Arrangement problem. We then
show that even if the domains of the Node Cover and Directed Hamiltonian Path
problems are restricted to planar graphs, the two problems remain NP-complete,
and that these and other graph problems remain NP-complete even when their
domains are restricted to graphs with low node degrees. For Graph 3-Colorability,
Node Cover, and Undirected Hamiltonian Circuit, we determine essentially the
lowest possible upper bounds on node degree for which the problems remain
NP-complete.
No comments:
Post a Comment