On search decision and the efficiency of polynomial-time algorithms

ABSTRACT

Recent advances in well-partial-order theory, especially the seminal contributions of Robertson and Seymour, have troubling consequences for those who would equate tractability with polynomial-time decidability. Specifically: many problems are now known to be decidable in low-degree polynomial time, but only by decision algorithms with overwhelmingly astronomical constants of proportionality, the existence of such a polynomial-time decision algorithm alone does not ensure that a corresponding search problem can be solved efficiently, and even if both a decision problem and a corresponding search problem can be shown to be polynomial-time computable, there is no guarantee that correct algorithms can be found or even recognized within any bounded amount of time. In this paper, we present a number of techniques for dealing with these remarkable features of algorithms based on well-partially-ordered sets. Our main results include a general strategy with which such algorithms can be made constructive. With the aid of this method, we demonstrate that low-degree polynomial-time algorithms are now known for almost all of the catalogued applications of RS posets. We also prove that, despite the nonconstructive nature of the well-partial-order theory on which this line of research is based, no RS poset application can settle P @@@@ N P non-constructively by any established method of argument.

REFERENCES

• AFL: D. Archdeacon, M. R. Fellows and M. A. Langston, "Fixed Genus Embedding in O(n4) Time," in preparation.
• BFL: D.J. Brown, M. R. Fellows and M. A. Langston, "Polynomial-Time Self- Reducibility: Theoretical Motivations and Practical Results," Int'l J. of Comp. Math., to appear.
• Bod1: H.L. Bodlaender, "Classes of Graphs with Bounded Tree-Width," Technical Report RUU-CS-86-22, Departmeat of Computer Science, University of Utrecht, 1986.
• Bod2: H. L. Bodlaender, "Improved Self- Reduction Algorithms for Graphs with Bounded Tree-Width," Technical Report RUU-CS-88-29, Department of Computer Science, University of Utrecht 1988.
• Bol: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• CEF: L. Clark, R. C. Entringer and M. R. Fellows, "Computational Complexity of Integrity," J. Combin. Math. Combin. Comput. 3 (1988), 549-560.
• CG: S. Cook and A. Gupta, private communication.
• DKL: 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.
• FKL: M. R. Fellows , N. G. Kinnersley , M. A. Langston, Finite-basis theorems and a computation-integrated approach to obstruction set isolation, Proceedings of the third conference on Computers and mathematics, p.37-45, May 1989, Boston, Massachusetts, United States
• FL1: M. R. Fellows , M. A. Langston, Nonconstructive advances in polynomial-time complexity, Information Processing Letters, v.26 n.3, p.155-162, Nov. 23, 1987
• FL2: Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
• FL3: Michael R. Fellows , Michael A. Langston, Layout permutation problems and well-partially-ordered sets, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.315-327, January 1988, Cambridge, Massachusetts, United States
• FL4: ---, "On Well-Partial-0rder Theory and Its Application to Combinatorial Problems of VLSI Design," Computer Science Technical Report CS- 88-188, Washington State University, 1988.
• FL5: M. R. Fellows , M. A. Langston, Fast self-reduction algorithms for combinatorial problems of VLSI design, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• FL6: Michael R. Fellows , Michael A. Langston, Fast Search Algorithms for Layout Permutation Problems, University of Tennessee, Knoxville, TN, 1990
• FRS: 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.
• FS: M.R. Fellows and S. S tueckle, "The Immersion Orde, r, Forbidden Subgraphs and the Comple:~Jty of Integrity," to appear.
• GJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Ha: W. Haken, "Theorie der Normalfi~chen,' Acta Maihematica 105 (1961), 245-375.
• Jo: David S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, v.8 n.2, p.285-303, June 1987 [doi>10.1016/0196-6774(87)90043-5]
• Ki: Nancy Gail Kinnersley , Michael A. Langston, Obstruction set isolation for layout permutation problems, 1989
• Le: L. A. Levin, "Universal Enumeration Problems," (Russian) Problemic Peredaci Informacii, Tom IX (1972), 115-116.
• MaS: F.S. Makedon and I. H. Sudborough, "On Minimizing Width in Linear Layouts," to appear.
• Mi: G.L. Miller, "Riemann's Hypothesis and Tests for PrimaJity," J. of Computer and Systems Science 13 (1976), 300-317.
• MRS: R. Motwani, A. Raghunathan, and H. Saran, "Constructive Results from Graph Minors: Linkless Embeddings," Proc. 29th IEEE $ymp. on Foundations of Computer Science (1988), 398- 409.
• Na: C. Nash-Williams, "On Well-Quasi- Ordering Infinite Trees," Proc. Cambridge Phil. So c. 61 (1965), 697-720.
• Ro: Arnold L. Rosenberg, Issues in the Study of Graph Embeddings, Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science, p.150-176, June 15-18, 1980
• RS1: N. Robertson and P. D. Seymour, "Disjoint Paths-a Survey," SIAM J. Alg. Disc. Meth. 6 (1985), 300-305.
• RS2: _____, "Graph Minors--a Survey," in Surveys in Combinatorics (I. Anderson, ed.), Cambridge Univ. Press, 1985.
• RS3: ---, "Graph Minors I. Excluding a Forest," J. Comb. Th. Set. B 35 (1983), 39-61.
• RS4: ---, "Graph Minors II. Algorithmic Aspects of Tree-Width," J. Algorithms 7 (1986), 309-322.
• RS5: N. Robertson , P. D. Seymour, Graph minors. IV. Tree-width and well-quasi-ordering, Journal of Combinatorial Theory Series B, v.48 n.2, p.227-254, Apr. 1990 [doi>10.1016/0095-8956(90)90120-O]
• RS6: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• RS7: ---, "Graph Minors XiII. The Disjoint Paths Problem," to appear.
• RS8: ---, "Graph Minors XVI. Wagner's Conjecture," to appear.
• Sc: C.P. Schnorr, "Optimal Algorithms for Self-Reducible Problems," Proc. ICALP (1976), 322-337.
• Wa: K. Wagner, "Uber Einer Eigenshaft der Ebener Complexe," Math. Ann. 14 (1937), 570-590.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory