Bipartitna dimenzija

U matematičkim oblastima teorije grafova i kombinatorne optimizacije, bipartitna dimenzija ili biklikni pokrivač broja grafa G = (V, E) je minimalan broj biklika (to je kompletni bipartitni podgraf), koji bi trebalo da pokrije sve grane u E. Kolekcija bikliknih pokrivača koji pokrivaju sve grane u G se zove biklikni pokrivač grana, ili ponekad biklikni pokrivač. Bipartitna dimenzija u G je često označena simbolom d(G).

Primer

Primeri bikliknog pokrivača grana su dati u sledećim dijagramima:

• Primer za bikliknu pokrivenost grana
• 
  Bipartitni graf...
• 
  ...i pokrivenost sa četiri biklika
• 
  crveni biklik pokrivenosti
• 
  plavi biklik pokrivenosti
• 
  zeleni biklik pokrivenosti
• 
  crni biklik pokrivenosti

Formule za bipartitne dimenzije za neki graf

Biklikna dimenzije za kompletan graf od n čvorova $K_n$ je $\lceil {\log }_{2}n\rceil$. Bipartitna dimenzija krunskog grafa sa 2n čvora jednak je $\sigma (n)$ gde je

$\sigma (n)=\min \{k\mid n\le (\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor })\}$

inverzna funkcija centralnog binomnog koeficijenta (Šablon:Harv). Fišburn i Hamer (Šablon:Harvtxt) su definisali bipartitnu dimenziju za neke posebne grafove. Na primer, put $P_n$ ima $d(P_n)=\lfloor n/2\rfloor$ i ciklus $C_n$ ima $d(C_n)=\lceil n/2\rceil$.

Izračunavanje bipartitne dimenzije

Zadatak izračunavanja bipartitne dimenzije za dati graf G je problem optimizacije. Problem rešavanja bipartitne dimenzije može se formulisati kao:

PRIMER: graf $G=(V,E)$ i pozitivan ceo broj $k$. PITANJE: Da li G zaista ima biklikni prekrivač grana koji sadrži najviše $k$ biklika?

Ovaj problem se javlja kao problem GT18 u knjizi Gerija i Džonsona o NP-kompletnosti, i dosta je direktna reformulacija drugog problema rešavanja porodice ograničenog skupa.

Bazni problem se pojavljuje kao problem SP7 u knjizi Gerija i Džonsona. Ovde, za porodicu $𝒮=\{S_1,\dots ,S_n\}$ podskupova ograničenog skupa $𝒰$, osnovni skup za $𝒮$ je još jedna porodica podskupova $ℬ=\{B_1,\dots ,B_{\ell }\}$ od $𝒰$ tako da svaki skup $S_i$ kao unija nekih osnovnih elemenata iz $ℬ$. Skup osnovnog problema se sada prikazuje ovako:

PRIMER: Ograničeni skup $𝒰$, porodica $𝒮=\{S_1,\dots ,S_n\}$ podskupova $𝒰$ i pozitivan ceo broj k. PITANJE: Da li postoji osnovni skup ne veći od $k$ za $𝒮$?

Ovaj problem je dokazan da je NP-kompletan od strane Orlina (Šablon:Harvtxt), čak i za bipartitne grafove. Stokmejer (Šablon:Harvtxt) je ranije dokazao da je NP-kompletnost formula osnovnog baznog problema. Problem ostaje NP-težak, čak i ako ograničimo našu pažnju na bipartitne grafove čija je bipartitna dimenzija zagarantovana da bude najviše $O(\log n)$, gde n označava veličinu datog problema (Šablon:Harv). Sa pozitivne strane, problem je rešiv u polinomijalnom vremenu na bipartitnom domino-slobodnim grafovima (Šablon:Harv).

Što se tiče postojanja približnih algoritama, Simon (Šablon:Harvtxt) je dokazao da problem ne može biti lepo objašnjen (ako se pretpostavi da je '''P''' ≠ '''NP'''). Zaista, bipartitnu dimenziju je NP-težak približio unutar $|V{|}^{1/3-ϵ}$ za svako ustaljeno $ϵ>0$, već za bipartitne grafove (Šablon:Harv). U suprotnosti sa time, dokazuje da je problem prilagodljiv ustaljenim parametrima je vežba dizajniranja jezgrovitih algoritama, kako se pojavljuje u udžbeniku Daunija i Felousa (Šablon:Harvtxt). Flajšner, Mudžuni i Zajder (Šablon:Harvtxt) takođe su obezbedili konkretnu granicu veličine rezultujećeg jezgra, što je u međuvremenu unapredio Nor et al (Šablon:Harvtxt). Zapravo, za dati bipartitni graf sa n čvorova, može se na vreme zaključiti da je $O(f(k))+n^3$ sa $f(k)=2^{k{2}^{k-1}+3k}$ nebitno da li je njegova bipartitna dimenzija najviše k (Šablon:Harv).

Aplikacije

Problem određivanja bipartitne dimenzije grafa se pojavljuje u raznim kontekstima računarstva. Na primer, u računarskim sistemima, različitim korisnicima sistema može biti dozvoljen ili odbijen pristup raznim resursima. U sistemu za kontrilu pristupa] zasnovanog na ulozi, uloga snabdeva pravo pristupa skupu resursa. Korisnik može da poseduje višestruke uloge i ima dozvolu da pristupi svim resursima koje mu odobravaju neke od njegovih uloga. Takođe, uloga može biti u vlasništvu više korisnika. Problem sa ulogama jeste naći minimalni skup resursa, tako da sve uloge svih korisnika pružaju pristup svim naznačenim resursima. Skup korisnika zajedno sa skupom resursa u sistemu prirodne indukcije bipartitni graf, čije grane predstavljaju dozvole. Svaki biklik u svom grafu je potencijalna uloga, a optimalno rešenje glavnog problema je upravo minimalni biklik pokrivača grana (Šablon:Harv).

Slični scenario se može naći i u kompjuterskoj bezbednosti, tačnije u emitovanju. U tom slučaju, više poruka mora biti pojedinačno poslato kompletu prijemnika, preko neproverenog kanala. Svaka poruka mora da bude kodirana korišćenjem nekog kriptografskog ključa poznatog samo onim prijemnicima kojima su namenjene. Svaki prijemnik može imati više ključeva za šifrovanje, a svaki ključ će biti raspodeljen između više prijemnika. Problem optimalnog ključa jeste pronaći minimalni skup ključeva za šifrovanje za obezbeđivanje sigurnog prenosa. Kao što je gore navedeno, problem se može podesiti pomoću bipartitnog grafa čiji se minimalni broj bikliknih prekrivača grana podudara sa reševanjem za optimalni problem pronalaženja ključa (Šablon:Harv).

Drugačija aplikacija može se naći u biologiji, gde se minimalni broj bikliknih pokrivenosti grana koristi u matematičkim obrascima leukocitnog antigena kod ljudi (HLA) (Šablon:Harv).

Reference

• Šablon:Citation
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Cite arxiv
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.
• Šablon:Citation.

Vanjske veze

• Šablon:En icon Blog entry about bipartite dimension Šablon:Webarchive (David Eppstein)