Problems remaining NP-complete for sparse or dense graphs

Ingo Schiermeyer

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 1, page 33-41
  • ISSN: 2083-5892

Abstract

top
For each fixed pair α,c > 0 let INDEPENDENT SET ( m ≤ c n α ) and INDEPENDENT SET ( m ≥ ( ⁿ ₂ ) - c n α ) be the problem INDEPENDENT SET restricted to graphs on n vertices with m ≤ c n α or m ≥ ( ⁿ ₂ ) - c n α edges, respectively. Analogously, HAMILTONIAN CIRCUIT ( m ≤ n + c n α ) and HAMILTONIAN PATH ( m ≤ n + c n α ) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≤ n + c n α edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) 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’.

How to cite

top

Ingo Schiermeyer. "Problems remaining NP-complete for sparse or dense graphs." Discussiones Mathematicae Graph Theory 15.1 (1995): 33-41. <http://eudml.org/doc/270554>.

@article{IngoSchiermeyer1995,
abstract = {For each fixed pair α,c > 0 let INDEPENDENT SET ($m ≤ cn^α$) and INDEPENDENT SET ($m ≥ (ⁿ₂) - cn^α$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m ≤ cn^α$ or $m ≥ (ⁿ₂) - 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 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) 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’.},
author = {Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Computational Complexity; NP-Completeness; Hamiltonian Circuit; Hamiltonian Path; Independent Set; computational complexity; NP-completeness; Hamiltonian path; independent set; NP-complete; Hamiltonian circuit},
language = {eng},
number = {1},
pages = {33-41},
title = {Problems remaining NP-complete for sparse or dense graphs},
url = {http://eudml.org/doc/270554},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Ingo Schiermeyer
TI - Problems remaining NP-complete for sparse or dense graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 33
EP - 41
AB - For each fixed pair α,c > 0 let INDEPENDENT SET ($m ≤ cn^α$) and INDEPENDENT SET ($m ≥ (ⁿ₂) - cn^α$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m ≤ cn^α$ or $m ≥ (ⁿ₂) - 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 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) 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’.
LA - eng
KW - Computational Complexity; NP-Completeness; Hamiltonian Circuit; Hamiltonian Path; Independent Set; computational complexity; NP-completeness; Hamiltonian path; independent set; NP-complete; Hamiltonian circuit
UR - http://eudml.org/doc/270554
ER -

References

top
  1. [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. [2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  3. [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. Zbl0789.05058
  4. [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. Zbl0047.17001
  5. [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. Zbl0746.05038
  6. [6] M. R. Garey and D. S. Johnson, Computers and I, A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979). Zbl0411.68039
  7. [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. Zbl0767.68057
  8. [8] O. Ore, Note on Hamiltonian circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928. 
  9. [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. Zbl0803.68052

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.