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:

Formule za bipartitne dimenzije za neki graf 

Biklikna dimenzije za kompletan graf od n čvorova  je . Bipartitna dimenzija krunskog grafa sa 2n čvora jednak je  gde je

inverzna funkcija centralnog binomnog koeficijenta (). Fišburn i Hamer () su definisali bipartitnu dimenziju za neke posebne grafove. Na primer, put  ima  i ciklus  ima .

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  i pozitivan ceo broj .
PITANJE: Da li G zaista ima biklikni prekrivač grana koji sadrži najviše  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  podskupova ograničenog skupa , osnovni skup za  je još jedna porodica podskupova  od  tako da svaki skup  kao unija nekih osnovnih elemenata iz . Skup osnovnog problema se sada prikazuje ovako:

PRIMER: Ograničeni skup , porodica  podskupova  i pozitivan ceo broj k.
PITANJE: Da li postoji osnovni skup ne veći od  za ?

Ovaj problem je dokazan da je NP-kompletan od strane Orlina (), čak i za bipartitne grafove. Stokmejer () 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 , gde n označava veličinu datog problema (). Sa pozitivne strane, problem je rešiv u polinomijalnom vremenu na bipartitnom domino-slobodnim grafovima ().

Što se tiče postojanja približnih algoritama, Simon () 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  za svako ustaljeno , već za bipartitne grafove ().
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 (). Flajšner, Mudžuni i Zajder () takođe su obezbedili konkretnu granicu veličine rezultujećeg jezgra, što je u međuvremenu unapredio Nor et al (). Zapravo, za dati bipartitni graf sa n čvorova, može se na vreme zaključiti da je  sa  nebitno da li je njegova bipartitna dimenzija najviše k ().

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 ().

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 ().

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) ().

Reference 
 
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 
 .
 .
 .
 .

Spoljašnje veze 
  Blog entry about bipartite dimension  (David Eppstein)

NP-kompletni problemi