Yoğun alt grafik - Dense subgraph

Bir grafik örneği ${ displaystyle G}$ yoğunluklu ${ displaystyle d_ {G} = 1,375}$ ve köşelerden kaynaklanan en yoğun alt grafiği ${ displaystyle b, c, d, e}$ ve ${ displaystyle h}$ yoğunluklu kırmızı renkte ${ displaystyle 1.4}$

İçinde bilgisayar Bilimi yüksek oranda bağlantılı alt grafikler kavramı sık sık ortaya çıkar. Bu kavram aşağıdaki gibi resmileştirilebilir. İzin Vermek ${ displaystyle G = (E, V)}$ fasulye yönsüz grafik ve izin ver ${ displaystyle S = (E_ {S}, V_ {S})}$ olmak alt grafik nın-nin ${ displaystyle G}$. Sonra yoğunluk nın-nin ${ displaystyle S}$ olarak tanımlandı ${ displaystyle d (S) = {| E_ {S} | over | V_ {S} |}}$.

En yoğun alt grafik problemi, maksimum yoğunluklu bir alt grafik bulmaktır. 1984 yılında Andrew V. Goldberg kullanarak maksimum yoğunluk alt grafiğini bulmak için bir polinom zaman algoritması geliştirdi. maksimum akış tekniği.

En yoğun k alt grafik

En yoğun alt grafik probleminin birçok varyasyonu vardır. Bunlardan biri en yoğun olanı ${ displaystyle k}$ Hedefin maksimum yoğunluk alt grafiğini tam olarak bulmak olduğu alt grafik problemi ${ displaystyle k}$ köşeler. Bu problem genelleştirir klik sorunu ve böylece NP-zor genel grafiklerde. En yoğun olana yaklaşan bir polinom algoritması vardır. ${ displaystyle k}$ bir oranda alt grafik ${ displaystyle n ^ {1/4 + epsilon}}$ her biri için ${ displaystyle epsilon> 0}$,^[1] kabul etmezken ${ displaystyle n ^ {1 / {{ text {polilog}} n}}}$- polinom zamandaki yaklaşık üstel zaman hipotezi yanlış.^[2] Daha zayıf bir varsayım altında ${ displaystyle NP nsubseteq bigcap _ { epsilon> 0} BPTIME (2 ^ {n ^ { epsilon}})}$, Hayır PTAS sorun için var.^[3]

Sorun şu durumda NP-zor olmaya devam ediyor iki parçalı grafikler ve akor grafikleri ama polinomdur ağaçlar ve bölünmüş grafikler.^[4] Problemin NP-zor mu yoksa polinom mu olduğu açıktır. (uygun) aralık grafikleri ve düzlemsel grafikler; ancak, alt grafiğin bağlanması gereken problemin bir varyasyonu düzlemsel grafiklerde NP-zordur.^[5]

En fazla yoğun k alt grafik

En yoğun olanın hedefi ${ displaystyle k}$ sorun en fazla maksimum yoğunluk alt grafiğini bulmaktır. ${ displaystyle k}$ köşeler. Anderson ve Chellapilla, eğer varsa, ${ displaystyle alpha}$ bu problem için yaklaşık değer, o zaman bu bir ${ displaystyle Theta ( alfa ^ {2})}$ en yoğun için yaklaşım ${ displaystyle k}$ alt grafik sorunu.

En azından en yoğun k alt grafik

En azından en yoğun ${ displaystyle k}$ problem en yoğun olana benzer şekilde tanımlanır ${ displaystyle k}$ alt grafik sorunu. Sorun NP-tamamlandı,^[6] ancak polinom zamanında 2-yaklaşımı kabul eder.^[7] Dahası, bu yaklaşım algoritmasının esasen mümkün olan en iyi olduğuna dair bazı kanıtlar vardır: Küçük Küme Genişleme Hipotezini varsaymak (hesaplama karmaşıklığı varsayımı, Benzersiz Oyunlar Varsayımı ), o zaman sorunu içeriye yaklaştırmak NP-zordur ${ displaystyle (2- epsilon)}$ her sabit için faktör ${ displaystyle epsilon> 0}$.^[8]

K-klik en yoğun alt grafik

Charalampos Tsourakakis tanıttı ${ displaystyle k}$-klik en yoğun alt grafik problemi. En yoğun alt grafik probleminin bu varyasyonu, indüklenen ortalama sayısını maksimize etmeyi amaçlamaktadır. ${ displaystyle k}$ klikler ${ displaystyle d_ {k} (S) = {| C_ {k} (S) | over | V_ {S} |}}$, nerede ${ displaystyle C_ {k} (S)}$ kümesidir ${ displaystyle k}$tarafından indüklenen klikler ${ displaystyle S}$. En yoğun alt grafik probleminin özel bir durum olarak elde edildiğine dikkat edin. ${ displaystyle k = 2}$. Bu genelleme, büyük ölçekli gerçek dünya ağlarından büyük yakın klikler çıkarmak için deneysel olarak başarılı bir çoklu zaman yaklaşımı sağlar.

Yerel olarak üstk en yoğun alt grafik

Qin vd. Her biri grafikte kendi yerel bölgesinde en yüksek yoğunluğa ulaşan bir grafikte top-k yerel olarak en yoğun alt grafik keşfi problemini ortaya koydu: ne aynı veya daha büyük yoğunluğa sahip herhangi bir süper grafiğin içinde ne de yoğunluğa sahip alt grafikleri içeriyor yerel en yoğun alt grafiğin geri kalanıyla gevşek bir şekilde bağlantılı. En yoğun alt grafik probleminin özel bir durum olarak elde edildiğine dikkat edin. ${ displaystyle k = 1}$. Bir grafikteki yerel olarak en yoğun alt grafikler kümesi polinom zamanda hesaplanabilir.

Referanslar

daha fazla okuma