Some NP-Complete Problems Similar to Graph Isomorphism
The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
The GRAPH ISOMORPHISM problem has so far resisted attempts at determining its complexity status—it has not been shown to be NP-complete nor in P. In this paper several altered or generalized versions of the ISOMORPHISM problem are presented and shown to be NP-complete. One of these is the problem of determining whether a given graph has a fixed-point-free automorphism. Some speculation is made on the possible implications of these results on deciding the complexity status of ISOMORPHISM. Various classes and hierarchies of problems in NP are discussed.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Although there are graph-based approaches that are potentially less vulnerable to such attacks, they are not feasible in practice [24] due to the NP nature of determining subgraph isomorphism [25,29,45].”
From Detecting Automatic Software Plagiarism via Token Sequence Normalization (2024) · cites this paper as [25]
Citations
Cites
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
The Complexity of Enumeration and Reliability Problems
Valiant, L. G. (1979) · SIAM Journal on Computing · doi:10.1137/0208032 · Cited by 2,076
On the Structure of Polynomial Time Reducibility
Ladner, R. E. (1975) · Journal of the ACM · doi:10.1145/321864.321877 · Cited by 781
Read, R. C., & Corneil, D. G. (1977) · Journal of Graph Theory · doi:10.1002/jgt.3190010410 · Cited by 453
A note on the graph isomorphism counting problem
Mathon, R. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90004-8 · Cited by 200
A Linear Time Algorithm for Deciding Interval Graph Isomorphism
Lueker, G. S., & Booth, K. S. (1979) · Journal of the ACM · doi:10.1145/322123.322125 · Cited by 192
A clique problem equivalent to graph isomorphism
Kozen, D. C. (1978) · ACM SIGACT News · doi:10.1145/990524.990529 · Cited by 26
Research works printed but not linked: 7
- L. Babai, On the isomorphism problem, Proc. FCT Conf., Poznań -Kórnik, 1977
- D. G. Corneil, Recent results on the graph isomorphism problem, Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1978), Congress. Numer., XXII, Utilitas Math., Winnipeg, Man., 1979, 13–31 81i:051130404.68054
- Garey Michael R., 1979, Computers and intractability
- Gorenstein P., 1968, Finite groups
- J. E. Hopcroft, J. K. Wong, Linear time algorithm for isomorphism of planar graphs: preliminary report, Sixth Annual ACM Symposium on Theory of Computing (Seattle, Wash., 1974), Assoc. Comput. Mach., New York, 1974, 172–184 55:69340369.05028 · DOI · Paper page
- Levi G., 1972, Calcolo, 9
- G. L. Miller, On the n**logn isomorphism technique, Proc. Tenth SIGACT Symp. on the Theory of Computing, 1978, 51–58, also Tech. Report 17, Univ. Rochester, 1976 · doi:10.1145/800133.804331
Cited by
Feder, T., & Vardi, M. Y. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794266766 · Cited by 1,030
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Babai, L., & Luks, E. M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808746 · Cited by 410
Detecting Automatic Software Plagiarism via Token Sequence Normalization
Sağlam, T., Brödel, M., Schmid, L., & Hahner, S. (2024) · Proceedings of the IEEE/ACM 46th International Conference on Software Engineering · doi:10.1145/3597503.3639192 · Cited by 9
Metadata
- Authors
- Lubiw, A.
- Corresponding author
- Lubiw, Anna
- ORCID
- Lubiw, Anna
- Venue
- SIAM Journal on Computing
- Published
- 1981-02
- Volume
- 10
- Issue
- 1
- Pages
- 11-21
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2041176939
- Semantic Scholar
- 39a2f3848f6c1c40dfa2bed0ca8b11a1a4871d79
- Cited by
- 144
- References
- 7
- Citations by year
- 2026: 2 · 2025: 3 · 2024: 1 · 2023: 4 · 2022: 5 · 2021: 3 · 2020: 4 · 2019: 5 · 2018: 6 · 2017: 5 · 2016: 12 · 2015: 6 · 2014: 7 · 2013: 6 · 2012: 4
- FWCI
- 2.33
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Keywords
- graph isomorphism, NP-completeness, fixed-point-free automorphisms, complexity classes, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.