DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  15(1) (1995)   33-41
DOI: 10.7151/dmgt.1004

PROBLEMS REMAINING NP-COMPLETE FOR SPARSE OR DENSE GRAPHS

Ingo Schiermeyer

Lehrstuhl C für Mathematik, Technische Hochschule Aachen
D-52056 Aachen, Germany

Abstract

For each fixed pair   α, c > 0   let INDEPENDENT SET ( m ≤ cnα) and INDEPENDENT SET (m ≥ (n2) - cnα) be the problem INDEPENDENT SET restricted to graphs on   n   vertices with   m ≤ cnα or   m ≥ (n2) - cnα   edges, respectively. Analogously, HAMILTONIAN CIRCUIT (m ≤ n + cnα) and HAMILTONIAN PATH (m ≤ n + cnα) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with   m ≤ n +cnα   edges. For each  ε > 0   let HAMILTONIAN CIRCUIT (m ≥ (1 - ε)(n2)) and HAMILTONIAN PATH ( m ≥ (1 - ε)(n2)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with   m ≥ (1 - ε)(n2)   edges.

We prove that these six restricted problems remain NP-complete. Finally, we consider sufficient conditions for a graph to have a Hamiltonian circuit. These conditions are based on degree sums and neighborhood unions of independent vertices, respectively. Lowering the required bounds the problem HAMILTONIAN CIRCUIT jumps from 'easy' to 'NP-complete'.

Keywords: Computational Complexity, NP-Completeness, Hamiltonian Circuit, Hamiltonian Path, Independent Set

1991 Mathematics Subject Classification: 05C, 68Q

References

[1] J. A. Bondy, Longest paths and cycles in graphs of high degree, Research Report CORR 80-16, Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada (1980).
[2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976).
[3] H. J. Broersma, J. van den Heuvel and H. J. Veldman, A generalization of Ore's Theorem involving neighborhood unions, Discrete Math. 122 (1993) 37-49, doi: 10.1016/0012-365X(93)90285-2.
[4] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
[5] E. Flandrin, H. A. Jung and H. Li, Hamiltonism, degree sum and neighborhood intersections, Discrete Math. 90 (1991) 41-52, doi: 10.1016/0012-365X(91)90094-I.
[6] M. R. Garey and D. S. Johnson, Computers and I, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
[7] J. Kratochvíl, P. Savický and Z. Tuza, One more occurrence of variables makes jump from trivial to NP-complete, SIAM J. Comput. 22 (1993) 203-210, doi: 10.1137/0222015.
[8] O. Ore, Note on Hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928.
[9] I. Schiermeyer, The   k-Satisfiability problem remains NP-complete for dense families, Discrete Math. 125 (1994) 343-346, doi: 10.1016/0012-365X(94)90175-9.