Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only the existence of polynomial-time decision algorithms. In this paper these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set that supports this general approach is defined and explored.

REFERENCES

• 1: ABELLO, J., FELLOWS, M., AND RICHMAN, F. A Robertson-Seymour poset in the subgroup structure of finite Abelian groups. To appear.
• 2: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 3: Esther M. Arkin, Complexity of cycle and path problems in graphs, 1986
• 4: ARNBORG, S., CORNEIL, D. G., AND PROSKUROWSKI, A. Complexity of finding embeddings in a k-tree. To appear.
• 5: BAREFOOT, C., ENTRINGER, R., AND SWART, H. Vulnerability in graphs--A comparative study. J. Comb. Math. Comb. Comput. 1 (1987), 13-22.
• 6: Daniel Bienstock , Clyde L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM Journal on Computing, v.17 n.1, p.53-76, Feb. 1988 [doi>10.1137/0217004]
• 7: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 8: BROWN, D. J., FELLOWS, i. R., AND LANGSTON, M.A. Polynomial-time self-reducibility: Theoretical motivations and practical results. Tech. Rep. CS-87-171. Computer Science Dept., Washington State Univ., Pullman, Wash., 1987.
• 9: BRYANT, R. L., FELLOWS, i. R., KINNERSLEY, N. G., AND LANGSTON, i. A. On finding obstruction sets and polynomial-time algorithms for gate matrix layout. In Proceedings of the 25th Allerton Conference on Communication, Control, and Computing (Urbana, Ill., Sept. 30-Oct. 2), 1987, pp. 397-398.
• 10: CLARK, L., ENTRINGER, R., AND FELLOWS, M.R. Computational complexity of integrity. J. Comb. Math. Comb. Comput. To appear.
• 11: CONWAY, J., AND GORDON, C. Knots and links in spatial graphs. J. Graph Theory 7 (1983), 445-453.
• 12: DEO, N., KRISHNAMOORTHY, M. S., AND LANGSTON, M.A. Exact and approximate solutions for the gate matrix layout problem. IEEE Trans. Comput. Aid. Des. CAD 6 (1987), 79-84.
• 13: ELLIS, J., SUDBOROUGH, I. H., AND TURNER, J. Graph separation and search number. To appear.
• 14: Martin Farber , Geňa Hahn , Pavol Hell , Donald Miller, Concerning the achromatic number of graphs, Journal of Combinatorial Theory Series B, v.40 n.1, p.21-39, Feb. 1986 [doi>10.1016/0095-8956(86)90062-6]
• 15: FELLOWS, i.R. Encoding graphs in gv. iahs. Ph.D. dissertation. Univ. of Calif., San Diego, San Diego, Calif. 1985.
• 16: 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
• 17: 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
• 18: Michael R. Fellows , Michael A. Langston, Fast Self-Reduction Algorithms for Combinatorical Problems of VLSI-Design, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.278-287, June 28-July 01, 1988
• 19: FELLOWS, M. R., HICKLING, F..~ND SYSLO, M. A topological parameterization and hard graph problems. Congressus Nurneranbiun. ~. _,
• 20: I. S. Filotti , Gary L. Miller , John Reif, On determining the genus of a graph in O(v O(g)) steps(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.27-37, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804395]
• 21: FRIEDMAN, H., ROBERTSON, N., AND SEYMOUR, P.D. The metamathematics of the graph minor theorem. In Applications of Logic to Combinatorics. AMS Contemporary Mathematics Series, American Mathematical Society, Providence, R.I. To appear.
• 22: 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
• 23: HAKEN, W. Theorie der Normalfliichen. Acta Math. 105 (1961), 245-375.
• 24: HELL, P., AND MILLER, D. Graphs with given achromatic number. Discrete Math. 16 (1976), 195-207.
• 25: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 26: HUNTER, R., RICHMAN, F., AND WALKER, E. Simply presented valuated Abelian p-groups. J. Algebra 49 (1977), 125-133.
• 27: Alon Itai , Michael Rodeh, Finding a minimum circuit in a graph, Proceedings of the ninth annual ACM symposium on Theory of computing, p.1-10, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803390]
• 28: 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]
• 29: MAKEDON, F. S., PAPADIMITRIOU, C. H., AND SUDBOROUGH, I. H. Topological band width, SIAM J. Algebraic Discrete Methods 6 (1985), 418-444.
• 30: MEGIDDO, N., HAKIMI, S. L., GAREY, M. R., JOHNSON, D. S., AND PAPADIMITRIOU, C.H. On the Complexity of Searching a Graph. IBM Res. Rep. ILl 4987, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1986.
• 31: MEYER, A., AND PATERSON, M. With what frequency are apparently intractable problems difficult. Comput. Sci. Dept., Tech. Rep. Massachusetts Institute of Technology, Cambridge, Mass., 1979.
• 32: MILNER, E. Basic WQO and BQO Theory. In Graphs and Orders, I. Rival, Ed. Reidel, Amsterdam, 1985.
• 33: NASH-WILLIAMS, C. On well-quasi-ordering infinite trees. Proc. Cambridge PhiL Soc. 61 (1965), 697-720.
• 33a: NESETRm, J., AND THOMAS, R. A note on spatial representation of graphs. Commentat. Math. Univ. Carolinae 26 (1985), 655-659.
• 34: RICHMAN, F. Computers, trees, and Abelian groups. To appear.
• 35: ROBERTSON, N., AND SEYMOUR, P. D. Disjoint paths~A survey. SIAM J. Algebraic Discrete Methods 6 (1985), 300-305.
• 36: ROBERTSON, N., AND SEYMOUR, P.D. Graph minors~A Survey. In Surveys in Combinatorics, I. Anderson, Ed. Cambridge Univ. Press, Cambridge, England, 1985, pp. 153-171.
• 37: ROBERTSON, N., AND SEYMOUR, P.D. Graph minors XIII. The disjoint paths problem. To appear.
• 38: ROBERTSON, N., AND SEYMOUR, P.D. Graph minors XVI. Wagner's conjecture. To appear.
• 39: ROGERS, L. Ulm's theorem for partially ordered structures related to simply presented Abelian p-groups. Trans. Am. Math. Soc. 227 (1977), 333-343.
• 40: SACHS, H. On spatial representations of finite graphs. In Colloquia Mathematica Societatis Janos Bolyai 37, Finite and Infinite Sets. Eger, Budapest, Hungary, 198 I, pp. 649-662.
• 41: SCHUBERT, H. Bestimmung der Primfaktorzerlegung von Verkettungen. Math. Z. 76 (1961), 116-148.
• 42: STILLWELL, J. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1980.
• 43: THOMAS, R. Graphs without K4 and well-quasi ordering. J. Comb. Theory, Series B 38 (1985), 240-247.
• 44: THOMASSEN, C. Graph families with the Erdrs-Prsa Property. J. Graph Theory. To appear.
• 45: WAGNER, K. Uber Einer Eigenschaft der Ebener Complexe. Math. Ann. 14 (1937), 570-590.
• 46: WELSH, D. J. Matroid Theory. Academic Press, Orlando, Fla., 1976.
• 47: Herbert S. Wilf, Finite lists of obstructions, American Mathematical Monthly, v.94 n.3, p.267-271, March 1987 [doi>10.2307/2323393]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification