Two Papers on Graph Embedding Problems.
Abstract
This report contains two independent papers on problems concerned with graph embedding-i.e., assignment of the vertices of a graph to points in a metric space subject to specified constraints. The first paper in this report, 'Embeddability of weighted graphs in k-space is strongly NP-hard,' examines the problem of assigning the vertices of a weighted graph to points in a k-dimensional Euclidean space subject to the constraint that any two vertices connected by an edge must be assigned to points whose distance is the weight of that edge. We prove (by reduction from 3-satisfiability) that it is NP-hard to determine whether such an assignment exists, even when k=1 and the edge weights are restricted to take on the values 1 and 2. The same reduction used in this proof forms the basis of proofs of the NP-completeness of several variants of the original problem. The second paper, 'Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time,' deals with the problem of bandwidth minimization, in which we are given a graph, G, and a positive integer, k, and whether it is possible to assign the vertices of G to distinct integers subject to the constraint that no edge of G may have its endpoints mapped to integers which differ by more than k. Although the general problem has been proven (by C. H. Papadimitriou) to be NP-complete, we show that it can be solved in polynomial time for any fixed value of k. As in the first paper, the methods used to achieve the principal result are extended to a number of related problems. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA081449
Entities
People
- James B. Saxe
Organizations
- Carnegie Mellon University