Michael R. Fellows
Michael A. Langston
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.
- 1 ABELLO, J., FELLOWS, M., AND RICHMAN, F. A Robertson-Seymour poset in the subgroup structure of finite Abelian groups. To appear.Google Scholar
- 2 ANGLUIN, D. Local and global properties in networks of processors. In Proceedings of the 12th ACM Symposium on Theory of Computing. ACM, New York, 1980, pp. 82-93. Google Scholar
- 3 ARKIN, E. Complexity of cycle and path problems in graphs. Ph.D. dissertation. Stanford Univ., Stanford, Calif., 1986. Google Scholar
- 4 ARNBORG, S., CORNEIL, D. G., AND PROSKUROWSKI, A. Complexity of finding embeddings in a k-tree. To appear.Google Scholar
- 5 BAREFOOT, C., ENTRINGER, R., AND SWART, H. Vulnerability in graphs--A comparative study. J. Comb. Math. Comb. Comput. 1 (1987), 13-22.Google Scholar
- 6 BIFNSTOCK, D., AND MONNA, C.L. On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. To appear. Google Scholar
- 7 BONDY, J., AND MURTY, U. Graph Theory with Applications. American Elsevier, New York, 1976. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 10 CLARK, L., ENTRINGER, R., AND FELLOWS, M.R. Computational complexity of integrity. J. Comb. Math. Comb. Comput. To appear.Google Scholar
- 11 CONWAY, J., AND GORDON, C. Knots and links in spatial graphs. J. Graph Theory 7 (1983), 445-453.Google Scholar
- 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.Google Scholar
- 13 ELLIS, J., SUDBOROUGH, I. H., AND TURNER, J. Graph separation and search number. To appear.Google Scholar
- 14 FARBER, i., HAHN, G., HELL, P., AND MILLER, D. Concerning the achromatic number of graphs. J. Comb. Theory, Series B 40 (1986), 21-39. Google Scholar
- 15 FELLOWS, i.R. Encoding graphs in gv. iahs. Ph.D. dissertation. Univ. of Calif., San Diego, San Diego, Calif. 1985.Google Scholar
- 16 FELLOWS, M. R., AND LANGSTON, M.A. Nonconstructive advances in polynomial-time complexity. Inf. Process. Lett. 26 (1987), 157-162. Google Scholar
- 17 FELLOWS, M. R., AND LANGSTON, i.A. Layout permutation problems and well-partially-ordered sets. In Proceedings of the 5th NIT Conference on Advanced Research in VLSI (Cambridge, Mass., Mar. 28-30). NIT Press, Cambridge, Mass., 1988, pp. 315-327. Google Scholar
- 18 FELLOWS, i. R., AND LANGSTON, M.A. Fast self-reduction algorithms for combinatorial problems of VLSI Design. In Proceedings of the 3rd International Workshop on Parallel Computation and VLSI Theory (,4 WOC) (Corfu Island, Greece, June 28-July 1), 1988. To appear. Google Scholar
- 19 FELLOWS, M. R., HICKLING, F..~ND SYSLO, M. A topological parameterization and hard graph problems. Congressus Nurneranbiun. ~. _,Google Scholar
- 20 FILOTTI, I. S., MILLER, G. L., AND REIF, J. i, ill determining the genus of a graph in O(V~t*)) steps. In Proceedings of the 1 lth ACM Sympo3,. .n on Theory of Computing (Atlanta, Ga., Apr. 3- May 2). ACM, New York, 1979, pp. 27-37. Google Scholar
- 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.Google Scholar
- 22 GAREY, M. R., AND JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP- Completeness. Freeman, San Francisco, Calif., 1979. Google Scholar
- 23 HAKEN, W. Theorie der Normalfliichen. Acta Math. 105 (1961), 245-375.Google Scholar
- 24 HELL, P., AND MILLER, D. Graphs with given achromatic number. Discrete Math. 16 (1976), 195-207.Google Scholar
- 25 HOPCROFT, J. E., AND ULLMAN, J.D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979. Google Scholar
- 26 HUNTER, R., RICHMAN, F., AND WALKER, E. Simply presented valuated Abelian p-groups. J. Algebra 49 (1977), 125-133.Google Scholar
- 27 ITAI, A., AND RODEH, M. Finding a minimum circuit in a graph. In Proceedings of the 9th ACM Symposium on Theory of Computing (Boulder, Colo., May 2-4). ACM, New York, 1977, pp. 1-10. Google Scholar
- 28 JOHNSON, D. S. The many faces of polynomial time. In The NP-Completeness Column: An Ongoing Guide. J. Algorithms 8 (1987), 285-303. Google Scholar
- 29 MAKEDON, F. S., PAPADIMITRIOU, C. H., AND SUDBOROUGH, I. H. Topological band width, SIAM J. Algebraic Discrete Methods 6 (1985), 418-444.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 32 MILNER, E. Basic WQO and BQO Theory. In Graphs and Orders, I. Rival, Ed. Reidel, Amsterdam, 1985.Google Scholar
- 33 NASH-WILLIAMS, C. On well-quasi-ordering infinite trees. Proc. Cambridge PhiL Soc. 61 (1965), 697-720.Google Scholar
- 33a NESETRm, J., AND THOMAS, R. A note on spatial representation of graphs. Commentat. Math. Univ. Carolinae 26 (1985), 655-659.Google Scholar
- 34 RICHMAN, F. Computers, trees, and Abelian groups. To appear.Google Scholar
- 35 ROBERTSON, N., AND SEYMOUR, P. D. Disjoint paths~A survey. SIAM J. Algebraic Discrete Methods 6 (1985), 300-305.Google Scholar
- 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.Google Scholar
- 37 ROBERTSON, N., AND SEYMOUR, P.D. Graph minors XIII. The disjoint paths problem. To appear.Google Scholar
- 38 ROBERTSON, N., AND SEYMOUR, P.D. Graph minors XVI. Wagner's conjecture. To appear.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 41 SCHUBERT, H. Bestimmung der Primfaktorzerlegung von Verkettungen. Math. Z. 76 (1961), 116-148.Google Scholar
- 42 STILLWELL, J. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1980.Google Scholar
- 43 THOMAS, R. Graphs without K4 and well-quasi ordering. J. Comb. Theory, Series B 38 (1985), 240-247.Google Scholar
- 44 THOMASSEN, C. Graph families with the Erdrs-Prsa Property. J. Graph Theory. To appear.Google Scholar
- 45 WAGNER, K. Uber Einer Eigenschaft der Ebener Complexe. Math. Ann. 14 (1937), 570-590.Google Scholar
- 46 WELSH, D. J. Matroid Theory. Academic Press, Orlando, Fla., 1976.Google Scholar
- 47 WmF, H. Finite lists of obstructions. Am. Math. Monthly 94 (1987), 267-271. Google Scholar
Index Terms
- Nonconstructive tools for proving polynomial-time decidability
Recommendations
Derandomizing polynomial identity tests means proving circuit lower bounds
We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, ...
Derandomizing polynomial identity tests means proving circuit lower bounds
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computingWe show that derandomizing Polynomial Identity Testing is, essentially, equivalent to proving circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or, even, nondeterministic subexponential time, infinitely ...
Reviews
Mark Allen Weiss
This paper examines a host of decision problems in graph theory, many of which deal with topology, and shows that most of them are solvable in O( n 3) time. Previously, many of these problems were not even known to be in NP, and some were not known to be decidable. The Robertson-Seymour theory of graph minors is used to prove the existence of polynomial-time algorithms for the problems discussed. Although the method does not yield constructive algorithms, such an algorithm has recently been discovered for one of the problems presented in this paper (linkless embeddings). Thus it is not unlikely that efficient constructive algorithms can be found for most of the problems shown in this paper. This paper is well written and extremely interesting. Although there are a multitude of references, the paper is largely self-contained and can be read on its own.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments