Article

Free access

Random instances of a graph coloring problem are hard

Authors:

Ramarathnam Venkatesan,

Leonid LevinAuthors Info & Claims

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

Pages 217 - 222

https://doi.org/10.1145/62212.62231

Published: 01 January 1988 Publication History

PDF eReader

Abstract

NP-complete problems should be hard on some (may be extremely rare) instances. But on generic instances many such problems (especially related to random graphs) have been proven easy. We show the intractability of random instances of a graph coloring problem by modifying the NP-completeness theorem.

References

[1]

L. Babai, P. Erdos, M. Selkow, Random Graph Isomorphism, $1AM Journal of Computing 9 (1980) 628-635.]]

Google Scholar

[2]

R. Berger, The undecidability of the domino problem, Mere. A met. Math. Soc. 66, (1966).]]

Google Scholar

[3]

M. Blum, S. Micali, How to generate Cryptographically Strong Sequences of Pseudo Random Bits, FOCS Syrup. Proc. (1982); SIAM J. on Computing, (1984)850-864.]]

Digital Library

Google Scholar

[4]

B. Bollob~s, Random Graphs, Academic Press (~98s).]]

Google Scholar

[5]

O. Goldreich, S. Goldwasser, S. Micali, How to Construct Random Functions, J. A CM 33 - 34 (1986), 792-807.]]

Digital Library

Google Scholar

[6]

Yu. G urevich, Complete and incomplete Randomized NP Problems ~8th Annual Sympo- Mum on Foundations o/ Computer Science (1987), 111-117.]]

Google Scholar

[7]

Yu. G urevich, S. Shelah, Expected computation time for Hamilton path problem, SIAM Journal of Computing 16 (1987) 486-502.]]

Digital Library

Google Scholar

[8]

N. Ikeno, A 6-symbol 10-state Universal Turing Machine, Proceedings, Institute of Electrical Communications, (1958) Tokyo.]]

Google Scholar

[9]

D. Johnson, The NP-completeness column-an ongoing guide, Journal of Algorithm.s 5 (1984), 284-299.]]

Digital Library

Google Scholar

[10]

J.C Lagarias, A.M. Odlyzko, Solving Low density subset sum problems, in Proc. 24th Ann. Syrup. on Foundations of Computer Science, (1983), pp 1-10.]]

Digital Library

Google Scholar

[11]

L.A. Levin, Average case complete problems, SIAM Journal of Computing 15 (1986) 285-6.]]

Digital Library

Google Scholar

[12]

R. Robinson, Undecidability and non-periodicity for tiling a p}ane, lnvencione Mathematicae 12 (1971) 177-209.]]

Google Scholar

[13]

A. Shamir, A polynomial algorithm for breaking the basic Markle-Hellman Cryptosystem, IEEE Symposium on Foundations of Computer Science (1982), 145-152.]]

Google Scholar

[14]

A.C. Yao, Theory and Applications of Trapdoor Functions, IEEE Syrup. on Foundations of. Computer Science (1982) 80-91.]]

Google Scholar

Cited By

View all

LEVIN LVENKATESAN R(2018)An Average Case NP-complete Graph Colouring ProblemCombinatorics, Probability and Computing10.1017/S096354831800012327:05(808-828)Online publication date: 2-Apr-2018
https://doi.org/10.1017/S0963548318000123
Ben-Sasson EChiesa AGenkin DTromer EKleinberg R(2013)Fast reductions from RAMs to delegatable succinct constraint satisfaction problemsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422481(401-414)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422481
Ansari M(2013)The graph coloring problem — Review of algorithms & neural networks and a new proposalIMPACT-201310.1109/MSPCT.2013.6782143(310-314)Online publication date: Nov-2013
https://doi.org/10.1109/MSPCT.2013.6782143
Show More Cited By

Index Terms

Random instances of a graph coloring problem are hard
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Models of computation
    1. Computability
      1. Turing machines

Recommendations

On the NP-Isomorphism Problem with Respect to Random Instances

This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomial-time computable and invertible bijections among NP-complete sets that preserve the underlying natural distributions on ...
Hard Instances of Hard Problems
STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science

This paper investigates the instance complexities of problems that are hard or weakly hard for exponential time under polynomial time, many-one reductions. It is shown that almost every instance of almost every problem in exponential time has ...
The complexity of choosing an H-colouring (nearly) uniformly at random

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

January 1988

553 pages

ISBN:0897912640

DOI:10.1145/62212

Chairman:
J'anos Simon
Univ. of Chicago, Illinois

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC88

Sponsor:

SIGACT

STOC88: 1988 Symposium on the Theory of Computing

May 2 - 4, 1988

Illinois, Chicago, USA

Acceptance Rates

STOC '88 Paper Acceptance Rate 53 of 192 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
740
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)15

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

LEVIN LVENKATESAN R(2018)An Average Case NP-complete Graph Colouring ProblemCombinatorics, Probability and Computing10.1017/S096354831800012327:05(808-828)Online publication date: 2-Apr-2018
https://doi.org/10.1017/S0963548318000123
Ben-Sasson EChiesa AGenkin DTromer EKleinberg R(2013)Fast reductions from RAMs to delegatable succinct constraint satisfaction problemsProceedings of the 4th conference on Innovations in Theoretical Computer Science10.1145/2422436.2422481(401-414)Online publication date: 9-Jan-2013
https://dl.acm.org/doi/10.1145/2422436.2422481
Ansari M(2013)The graph coloring problem — Review of algorithms & neural networks and a new proposalIMPACT-201310.1109/MSPCT.2013.6782143(310-314)Online publication date: Nov-2013
https://doi.org/10.1109/MSPCT.2013.6782143
Musliu NSchwengerer M(2013)Algorithm Selection for the Graph Coloring ProblemRevised Selected Papers of the 7th International Conference on Learning and Intelligent Optimization - Volume 799710.1007/978-3-642-44973-4_42(389-403)Online publication date: 7-Jan-2013
https://dl.acm.org/doi/10.1007/978-3-642-44973-4_42
Makhlin A(2013)On the Encoding Invariance of Polynomial Time Computable Distribution EnsemblesComputer Science – Theory and Applications10.1007/978-3-642-38536-0_17(195-202)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38536-0_17
Smith-Miles KLopes L(2012)Measuring instance difficulty for combinatorial optimization problemsComputers and Operations Research10.1016/j.cor.2011.07.00639:5(875-889)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.cor.2011.07.006
Goldreich O(2011)Notes on Levin's theory of average-case complexityStudies in complexity and cryptography10.5555/2028116.2028139(233-247)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2028116.2028139
Goldreich O(2011)Notes on Levin’s Theory of Average-Case ComplexityStudies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation10.1007/978-3-642-22670-0_21(233-247)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22670-0_21
Grigoriev DShpilrain V(2010)Authentication schemes from actions on graphs, groups, or ringsAnnals of Pure and Applied Logic10.1016/j.apal.2010.09.004162:3(194-200)Online publication date: Dec-2010
https://doi.org/10.1016/j.apal.2010.09.004
Szöllösi LMarosits TFehér GRecski A(2007)Fast digital signature algorithm based on subgraph isomorphismProceedings of the 6th international conference on Cryptology and network security10.5555/1778554.1778558(34-46)Online publication date: 8-Dec-2007
https://dl.acm.org/doi/10.5555/1778554.1778558
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the NP-Isomorphism Problem with Respect to Random Instances

Hard Instances of Hard Problems

The complexity of choosing an H-colouring (nearly) uniformly at random