Discussiones Mathematicae Graph Theory 15(1) (1995)
33-41
DOI: https://doi.org/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. |
Close