Complementul hamiltonian

Problema complementului hamiltonian este problema de a găsi numărul minim de muchii care trebuie adăugate unui grafic pentru a-l face hamiltonian .

Este clar că problema este în general NP-hard (deoarece soluția ei răspunde la problema NP-complet de a determina dacă un grafic are un ciclu hamiltonian ). Problema decidabilitate aferentă , dacă adăugarea K muchii la un graf dat poate produce un graf hamiltonian, este NP-complet.

Mai mult, Wu, Lu și Li au arătat că existența unor algoritmi eficienți cu un coeficient constant de aproximare pentru această problemă este puțin probabilă [1] .

Problema poate fi rezolvată în timp polinomial pentru unele clase de grafice, care includ grafice paralel-seriale [2] și generalizările lor [3] care includ grafice outerplanare . Aceste clase includ, de asemenea , grafice cu linii de arbore [4] [5] și cactusi [6] .

Gamarnik și Sviridenko au folosit o problemă de arbore de timp liniar pentru a studia numărul asimptotic de muchii care trebuie adăugate la graficele aleatoare rare pentru a le face Hamiltoniene [7] .

Note

  1. ↑ Wu, Lu, Lee, 2000 , p. 156 - 167.
  2. ↑ Takamizawa, Nisizeki și Saito, 1982 , p. 623–641.
  3. ↑ Kornienko, 1984 , p. 109-111.
  4. ↑ Raychaudhuri, 1995 , p. 299 - 306.
  5. ↑ Agnetis, Detti, Meloni, Pacciarelli, 2001 , p. 17 - 24.
  6. ↑ Detti, Meloni, 2004 , p. 197 - 215.
  7. ↑ Gamarnik, Sviridenko, 2005 , p. 139-158.

Literatură