Dimensiunea graficului intervalului

În teoria grafurilor, dimensiunea de interval a unui graf  este un invariant de graf introdus de Fred S. Roberts în 1969.

Dimensiunea de interval a unui grafic este dimensiunea minimă în care un grafic dat poate fi reprezentat ca un grafic al intersecțiilor de hiperdreptunghiuri (adică paralelipipede dreptunghiulare multidimensionale) cu muchii paralele cu axele. Adică trebuie să existe o corespondență unu-la-unu între vârfurile graficului și un set de hiperdreptunghiuri, astfel încât dreptunghiurile să se intersecteze dacă și numai dacă există o muchie care conectează vârfurile corespunzătoare.

Exemple

Figura prezintă un grafic cu șase vârfuri și o reprezentare a acestui grafic ca un grafic de intersecție a dreptunghiurilor (bidimensionale obișnuite). Acest grafic nu poate fi reprezentat ca un grafic al intersecțiilor dreptunghiurilor de dimensiune mai mică (în acest caz, segmente), deci dimensiunea intervalului a graficului este de două.

Roberts [1] a arătat că un grafic 2n - vertex format prin ștergerea unei potriviri perfecte dintr-un graf complet cu 2n-vertex are dimensiunea intervalului exact n  -orice pereche de vârfuri neconectate trebuie reprezentată ca hiperdreptunghiuri, care trebuie separate într-un mod diferit decât altă pereche de dimensiuni. Reprezentarea hiperdreptunghiulară a acestui grafic cu dimensiunea exact n poate fi găsită prin îngroșarea fiecăreia dintre cele 2n fețe ale hipercubului n - dimensional într-un hiperdreptunghi. Ca urmare a acestui rezultat, astfel de grafice au început să fie numite grafice Roberts [2] , deși sunt mai bine cunoscute ca grafice „de petrecere” și pot fi, de asemenea, tratate ca grafice Turan T (2 n , n ).

Relația cu alte clase de grafice

Un grafic are dimensiunea intervalului de cel mult una dacă și numai dacă este un grafic cu intervale . Dimensiunea de interval a unui grafic arbitrar G  este numărul minim de grafice de interval cu același set de vârfuri (ca G ) astfel încât intersecția seturilor de muchii ale graficelor de interval dă G . Orice grafic planar are dimensiunea intervalului de cel mult două [3] , iar orice grafic planar are dimensiunea intervalului de cel mult trei [4] .

Dacă un grafic bipartit are o dimensiune a intervalului de doi, acesta poate fi reprezentat ca un grafic al intersecțiilor segmentelor paralele cu axele din plan [5] .

Rezultate algoritmice

Multe probleme de grafice pot fi rezolvate sau aproximate mai eficient pe grafice cu dimensiunea intervalului limitat. De exemplu, cea mai mare problemă a clicei poate fi rezolvată în timp polinomial pentru grafice cu dimensiunea intervalului limitat [6] . Pentru alte probleme de pe grafice, o soluție sau o aproximare eficientă poate fi găsită dacă reprezentarea este sub forma unei intersecții de hipermogoedre de dimensiuni joase [7] .

Cu toate acestea, găsirea unor astfel de reprezentări poate fi dificilă - verificarea dacă dimensiunea intervalului unui grafic dat depășește o valoare predeterminată K este o problemă NP-completă , chiar și pentru K = 2 [8] . Chandran, Francis și Sivadasan [9] au descris algoritmi pentru găsirea reprezentărilor grafice de intersecție hiperdreptunghiulare ale graficelor arbitrare cu o dimensiune care se află în factorul logaritmic al celei mai mari puteri a graficului . Acest rezultat oferă o limită superioară a dimensiunii intervalului a graficului.

În ciuda dificultății pentru parametrii naturali, dimensiunea de interval a unui grafic este o problemă rezolvabilă cu parametru fix dacă parametrizarea este efectuată în funcție de numărul de acoperire a vârfurilor graficului de intrare [10] .

Note

  1. ↑ Roberts, 1969 .
  2. ↑ De exemplu, a se vedea articolele lui Chandran, Francis și Sivadasan (2010 ), Chandran și Sivadasan Chandran, Sivadasan (2007 ).
  3. ↑ Scheinerman, 1984 .
  4. ↑ Thomassen, 1986 .
  5. ↑ Bellantoni, Hartman, Przytycka, Whitesides, 1993 .
  6. ↑ Chandran, Francis și Sivadasan (2010 ) au remarcat că acest lucru rezultă din faptul că aceste grafice au un număr polinom de clicuri maxime . Reprezentarea explicită ca o intersecție a hiperdreptunghiurilor nu necesită enumerarea tuturor clicurilor maxime.
  7. ↑ A se vedea, de exemplu, Agarwal, van Kreveld, Suri (1998 ) și Berman, DasGupta, Muthukrishnan, Ramaswami (2001 ) pentru cele mai mari aproximări de mulțimi independente pentru graficele de intersecție dreptunghiulară și Chlebík, Chlebíková (2005 ) pentru o discuție despre dificultatea aproximarea acestor probleme pentru dimensiuni mari
  8. ↑ Cozzens (1981 ) a arătat că calcularea dimensiunii intervalului unui grafic este o problemă NP-completă. Yannakakis (1982 ) a arătat că chiar și verificarea dacă dimensiunea intervalului nu depășește 3 este NP-hard. În cele din urmă, Kratochvíl (1994 ) a arătat că recunoașterea unei dimensiuni de interval = 2 este o problemă NP-hard.
  9. ↑ Chandran, Francis, Sivadasan, 2010 .
  10. ↑ Adiga, Chitnis, Saurabh, 2010 .

Literatură