Klik genişliği - Clique-width

Bir inşaat mesafe kalıtsal grafik ayrık birleşimler, yeniden etiketlemeler ve etiket birleştirmelerle klik genişliği 3. Köşe etiketleri renklerle gösterilmiştir.

İçinde grafik teorisi, klik genişliği bir grafik grafiğin yapısal karmaşıklığını tanımlayan bir parametredir; yakından ilgili ağaç genişliği, ancak ağaç genişliğinden farklı olarak, yoğun grafikler Oluşturmak için gereken minimum etiket sayısı olarak tanımlanır. aşağıdaki 4 işlem vasıtasıyla:

  1. Yeni bir köşe oluşturulması v etiketli ben ( not alınmış i (v) )
  2. İki etiketli grafiğin ayrık birleşimi G ve H (belirtilen )
  3. Etiketli her tepe noktasından bir kenar ile birleşmek ben etiketli her köşeye j (belirtilen η (i, j)), nerede
  4. Etiket yeniden adlandırılıyor ben etiketlemek j (belirtilen ρ(ben,j) )

Sınırlı klik genişliği grafikleri şunları içerir: kograflar ve mesafe kalıtsal grafikler. Olmasına rağmen NP-zor Sınırsız olduğunda ve sınırlı olduğunda polinom zamanında hesaplanıp hesaplanamayacağı bilinmeyen klik genişliğini hesaplamak, verimli yaklaşım algoritmaları klik genişliği bilinmektedir. bu algoritmalara ve Courcelle teoremi, gelişigüzel grafikler için NP-zor olan birçok grafik optimizasyon problemi, sınırlı klik genişliği grafiklerinde hızla çözülebilir veya tahmin edilebilir.

Klik genişliği kavramının temelini oluşturan inşaat dizileri, Courcelle, Engelfriet ve Rozenberg, 1990[1] ve tarafından Wanke (1994). "Clique-width" adı, farklı bir kavram için kullanılmıştır. Chlebíková (1992). 1993 yılına gelindiğinde, terimin şimdiki anlamı zaten vardı.[2]

Özel grafik sınıfları

Kograflar tam olarak klik genişliğine sahip grafiklerdir 2.[3] Her mesafe kalıtsal grafik en fazla klik genişliğine sahiptir 3. Bununla birlikte, birim aralıklı grafiklerin klik genişliği sınırsızdır (ızgara yapılarına göre).[4] Benzer şekilde, iki taraflı permütasyon grafiklerinin klik genişliği sınırsızdır (benzer ızgara yapısına göre).[5] Dört köşeli akordsuz bir yola izomorfik indüklenmiş alt grafik içermeyen grafikler olarak kografların karakterizasyonuna dayanarak, yasaklı indüklenmiş alt grafikler tarafından tanımlanan birçok grafik sınıfının klik genişliği sınıflandırılmıştır.[6]

Sınırlı klik genişliğine sahip diğer grafikler şunları içerir: kyaprak güçleri sınırlı değerler için k; bunlar indüklenmiş alt grafikler bir ağacın yapraklarından T içinde grafik gücü Tk. Bununla birlikte, sınırsız üslere sahip yaprak güçleri, sınırlı klik genişliğine sahip değildir.[7]

Sınırlar

Courcelle ve Olariu (2000) ve Corneil ve Rotics (2005) belirli grafiklerin klik genişliğinde aşağıdaki sınırları kanıtladı:

  • Bir grafiğin en fazla klik genişliği varsa ko zaman her biri indüklenmiş alt grafik grafiğin.[8]
  • tamamlayıcı grafik klik genişliği grafiğinin k en fazla klik genişliğine sahiptir 2k.[9]
  • Grafikleri ağaç genişliği w en fazla klik genişliğine sahip 3 · 2w − 1. Bu sınırdaki üstel bağımlılık gereklidir: klik genişliği katlanarak ağaç genişliklerinden daha büyük olan grafikler vardır.[10] Diğer yönde, sınırlı klik genişliğine sahip grafikler sınırsız ağaç genişliğine sahip olabilir; Örneğin, n-vertex tam grafikler klik genişliğinde 2 ama üç genişlikte n − 1. Bununla birlikte, klik genişliği grafikleri k yok tam iki parçalı grafik Kt,t bir alt grafik olarak en fazla ağaç genişliği var 3k(t − 1) − 1. Bu nedenle, her aile için seyrek grafikler, sınırlı ağaç genişliğine sahip olmak, sınırlı klik genişliğine sahip olmaya eşdeğerdir.[11]
  • Başka bir grafik parametresi olan sıra genişliği, her iki yönde de klik genişliği ile sınırlıdır: sıra genişliği ≤ klik genişliği ≤ 2sıra genişliği + 1.[12]

Ek olarak, bir grafik G klik genişliğine sahiptir k, sonra grafik gücü Gc en fazla klik genişliğine sahiptir 2kck.[13] Ağ genişliğinden klik genişliği sınırında ve grafik güçlerinin klik genişliği sınırında üstel bir boşluk olmasına rağmen, bu sınırlar birbirini birleştirmez: G ağaç genişliği var w, sonra Gc en fazla klik genişliğine sahiptir 2(c + 1)w + 1 − 2, ağ genişliğinde yalnızca tek bir üstel.[14]

Hesaplama karmaşıklığı

Soru, Web Fundamentals.svgMatematikte çözülmemiş problem:
Sınırlı klik genişliğinin grafikleri polinom zamanda tanınabilir mi?
(matematikte daha fazla çözülmemiş problem)

Birçok optimizasyon sorunu NP-zor daha genel grafik sınıfları için verimli bir şekilde çözülebilir: dinamik program Sınırlı klik genişliği grafikleri üzerinde, bu grafikler için bir yapım sırası bilindiğinde.[15][16] Özellikle her biri grafik özelliği MSO olarak ifade edilebilir1 monadik ikinci derece mantık (köşe kümeleri üzerinde nicelendirmeye izin veren bir mantık biçimi), sınırlı klik genişliğindeki grafikler için bir doğrusal zaman algoritmasına sahiptir. Courcelle teoremi.[16]

Optimum bulmak da mümkündür grafik renklendirmeleri veya Hamilton döngüleri Polinom zamandaki sınırlı klik genişliği grafikleri için, bir inşa dizisi bilindiğinde, ancak polinomun üssü klik genişliği ile arttığında ve hesaplama karmaşıklığı teorisinden elde edilen kanıtlar, bu bağımlılığın muhtemelen gerekli olduğunu gösterir.[17]Sınırlı klik genişliğinin grafikleri χsınırlı yani kromatik sayıları, en fazla, en büyük kliklerinin boyutunun bir fonksiyonudur.[18]

Üç klik genişliğinin grafikleri tanınabilir ve bunlar için bir yapı dizisi, aşağıdakilere dayalı bir algoritma kullanılarak polinom zamanında bulunabilir. bölünmüş ayrışma.[19]Sınırsız klik genişliğine sahip grafikler için, NP-zor klik genişliğini tam olarak hesaplamak ve ayrıca alt doğrusal toplamsal hata ile bir yaklaşım elde etmek için NP-zordur.[20] Bununla birlikte, klik genişliği sınırlandırıldığında, polinom zamanında sınırlı genişlikte (gerçek klik genişliğinden katlanarak daha büyük) bir yapım dizisi elde etmek mümkündür.[21] Tam klik genişliğinin veya buna daha sıkı bir yaklaşımın hesaplanıp hesaplanamayacağı açık kalır. sabit parametreli izlenebilir zaman, klik genişliğindeki her sabit sınır için polinom zamanda hesaplanıp hesaplanamayacağı veya hatta klik genişliği dörtlü grafiklerin polinom zamanında tanınabilir olup olmadığı.[20]

Ağaç genişliğiyle ilişkisi

Sınırlı klik genişliği grafiklerinin teorisi, sınırlı klik genişliğinin grafikleri için olana benzer. ağaç genişliği, ancak ağaç genişliğinin aksine, yoğun grafikler. Bir grafik ailesi klik genişliğini sınırlamışsa, o zaman sınırlanmış ağaç genişliği veya her tam iki parçalı grafik ailedeki bir grafiğin alt resmi.[11] Ağaç genişliği ve klik genişliği de teori yoluyla birbirine bağlanır. Çizgi grafikleri: bir grafik ailesi, ancak ve ancak çizgi grafiklerinin klik genişliğini sınırlandırması durumunda, ağaç genişliğini sınırlamıştır.[22]

Notlar

  1. ^ Courcelle, Engelfriet ve Rozenberg (1993).
  2. ^ Courcelle (1993).
  3. ^ Courcelle ve Olariu (2000).
  4. ^ Golumbic ve Rotics (2000).
  5. ^ Brandstädt ve Lozin (2003).
  6. ^ Brandstädt vd. (2005); Brandstädt vd. (2006).
  7. ^ Brandstädt ve Hundt (2008); Gurski ve Wanke (2009).
  8. ^ Courcelle ve Olariu (2000), Sonuç 3.3.
  9. ^ Courcelle ve Olariu (2000) Teorem 4.1.
  10. ^ Corneil ve Rotics (2005), güçlendirme Courcelle ve Olariu (2000) Teorem 5.5.
  11. ^ a b Gurski ve Wanke (2000).
  12. ^ Oum ve Seymour (2006).
  13. ^ Todinca (2003).
  14. ^ Gurski ve Wanke (2009).
  15. ^ Cogis ve Thierry (2005).
  16. ^ a b Courcelle, Makowsky ve Rotics (2000).
  17. ^ Fomin vd. (2010).
  18. ^ Dvořák ve Král '(2012).
  19. ^ Corneil vd. (2012).
  20. ^ a b Fellows ve ark. (2009).
  21. ^ Oum ve Seymour (2006); Hliněný ve Oum (2008); Oum (2009).
  22. ^ Gurski ve Wanke (2007).

Referanslar