Abstract
In a recent series of papers [FL1, FL2, FL3], we have proven the existence of decision algorithms with low-degree polynomial running times for a number of well-studied VLSI layout, placement and routing problems. These results make use of the powerful Robertson-Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. In the present paper, we study the complexity of construction versions of these problems, focusing on efficient self-reduction strategies. We introduce a notion of fast self-reduction in this setting and develop a general technique, which we term scaffolding, that is useful in the design of fast self-reduction algorithms.
This author's research is supported in part by the Sandia University Research Program and by the National Science Foundation under grant MIP-8603879.
This author's research is supported in part by the Washington State Technology Center and by the National Science Foundation under grants ECS-8403859 and MIP-8603879.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
K. Abrahamson, M. R. Fellows, M. A. Langston and B. Moret, “Constructive Complexity,” to appear.
S. Arnborg and A. Proskurowski, “Linear Time Algorithms for NP-hard Problems on Graphs Embedded in k-trees,” TRITA-NA-8404, The Royal Institute of Technology (1984).
S. R. Buss and M. R. Fellows, “Achieving the Robertson-Seymour Bounds: k-Feedback and Related Vertex Sets,” to appear.
R. L. Bryant, M. R. Fellows, N. G. Kinnersley and M. A. Langston, “On Finding Obstruction Sets and Polynomial-Time Algorithms for Gate Matrix Layout,” Proc. 25th Allerton Conf. on Communication, Control, and Computing (1987), 397–398.
D. J. Brown, M. R. Fellows and M. A. Langston, “Polynomial-Time Self-Reducibility: Theoretical Motivations and Practical Results,” Computer Science Technical Report CS-87-171, Washington State University, 1987.
M. W. Bern, E. L. Lawler and A. L. Wong, “Why Certain Subgraph Computations Require Only Linear Time,” Proc. 26th IEEE Symposium the Foundations of Computer Science (1985), 117–125.
H. L. Bodlaender, “Classes of Graphs with Bounded Tree-Width,” Technical Report RUU-CS-86-22, Department of Computer Science, University of Utrecht, 1986.
B. Bollabás, Extremal Graph Theory, Academic Press, New York, 1978.
M. Blum and S. Rudich, private communication.
N. Deo, M. S. Krishnamoorthy and M. A. Langston, “Exact and Approximate Solutions for the Gate Matrix Layout Problem,” IEEE Trans. on Computer-Aided Design 6 (1987), 79–84.
J. Ellis, I. H. Sudborough and J. Turner, “Graph Separation and Search Number,” to appear.
M. R. Fellows, “Applications of the Robertson-Seymour Theorems: A Survey,” to appear.
M. R. Fellows and M. A. Langston, “Nonconstructive Advances in Polynomial-Time Complexity,” Info. Proc. Letters 26 (1987), 157–162.
—, “Nonconstructive Tools for Proving Polynomial-Time Decidability,” J. of the ACM, to appear.
—, “Layout Permutation Problems and Well-Partially-Ordered Sets,” Proc. 5th MIT Conf. on Advanced Research in VLSI (1988), to appear.
H. Friedman, N. Robertson and P. D. Seymour, “The Metamathematics of the Graph Minor Theorem,” in Applications of Logic to Combinatorics, American Math. Soc., Providence, RI, to appear.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
E. M. Gurari and I. H. Sudborough, “Improved Dynamic Programming Algorithms for Bandwidth Minimization and the Min Cut Linear Arrangement Problem,” J. of Algorithms 5 (1984), 531–546.
D. S. Johnson, “The Many Faces of Polynomial Time,” in The NP-Completeness Column: An Ongoing Guide, J. Algorithms 8 (1987), 285–303.
T. Kashiwabara and T. Fujisawa, “NP-completeness of the Problem of Finding a Minimum-Clique-Number Interval Graph Containing a Given Graph as a Subgraph,” Proc. IEEE Symp. on Circuits and Systems (1979), 657–660.
D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973.
M. Kirousis and C. H. Papadimitriou, “Searching and Pebbling,” Technical Report, National Technical University, Athens, Greece, 1983.
R. M. Karp, E. Upfal and A. Wigderson, “Are Search and Decision Problems Computationally Equivalent,” Proc. 17th ACM Symp. on Theory of Computing (1985), 464–475.
T. Lengauer, “Black-White Pebbles and Graph Separation,” Acta Informatica 16 (1981), 465–475.
W. Mader, “A Reduction Method for Edge-Connectivity in Graphs,” Annals of Disc. Math 3 (1978), 145–164.
F. S. Makedon and I. H. Sudborough, “On Minimizing Width in Linear Layouts,” to appear.
N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, “On the Complexity of Searching a Graph,” IBM Research Report RJ 4987, 1986.
Z. Miller and I. H. Sudborough, “Polynomial Algorithms for Recognizing Small Cutwidth in Hypergraphs,” to appear.
C. Nash-Williams, “On Well-Quasi-Ordering Infinite Trees,” Proc. Cambridge Phil. Soc. 61 (1965), 697–720.
A. Rosenberg, “Issues in the Study of Graph Embeddings,” Lecture Notes in Computer Science 100 (1981), 150–176.
N. Robertson and P. D. Seymour, “Disjoint Paths-a Survey,” SIAM J. Alg. Disc. Meth. 6 (1985), 300–305.
—, “Graph Minors—a Survey,” in Surveys in Combinatorics (I. Anderson, ed.), Cambridge Univ. Press, 1985.
—, “Graph Minors I. Excluding a Forest,” J. Comb. Th. Ser. B 35 (1983), 39–61.
—, “Graph Minors IV. Tree-Width and Well-Quasi-Ordering,” to appear.
—, “Graph Minors XIII. The Disjoint Paths Problem,” to appear.
—, “Graph Minors XVI. Wagner's Conjecture,” to appear.
D. Seese, “Tree-Partite Graphs and the Complexity of Algorithms,” Preprint P-Math-08/86, Karl-Weierstrass-Institut für Mathematik, Akademie der Wissenschaften der DDR, 1986.
P. Scheffler and D. Seese, “Graphs of Bounded Tree-Width and Linear-Time Algorithms for NP-Complete Problems,” manuscript, 1986.
K. Wagner, “Uber Einer Eigenshaft der Ebener Complexe,” Math. Ann. 14 (1937), 570–590.
T. V. Wimer, S. T. Hedetniemi and R. Laskar, “A Methodology for Constructing Linear Graph Algorithms,” Congressus Numerantium 50 (1985), 43–60.
T. V. Wimer, “Linear Algorithms on k-Terminal Graphs,” Ph.D. Dissertation, Clemson University, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fellows, M.R., Langston, M.A. (1988). Fast self-reduction algorithms for combinatorial problems of VLSI design. In: Reif, J.H. (eds) VLSI Algorithms and Architectures. AWOC 1988. Lecture Notes in Computer Science, vol 319. Springer, New York, NY. https://doi.org/10.1007/BFb0040395
Download citation
DOI: https://doi.org/10.1007/BFb0040395
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-96818-6
Online ISBN: 978-0-387-34770-7
eBook Packages: Springer Book Archive