Pertanyaan tentang treewidth grafik. Grafik dengan treewidth rendah mengakui algoritma divide-and-conquer yang cepat untuk banyak masalah grafik yang NP-hard pada grafik umum.
Pertanyaan saya hari ini (seperti biasa) agak konyol; tapi saya akan meminta Anda untuk mempertimbangkannya. Saya ingin tahu tentang asal-usul dan / atau motivasi di balik konsep treewidth. Saya yakin mengerti bahwa ini digunakan dalam algoritma FPT, tapi saya tidak berpikir bahwa itulah alasan...
ST-Konektivitas adalah masalah menentukan apakah ada jalur terarah antara dua simpul dan t dalam grafik berarah G ( V , E ) . Apakah masalah ini dapat diselesaikan di logspace, adalah masalah terbuka yang sudah lama ada. Ini disebut N L vs L masalah.ssstttG(V,E)G(V,E)G(V,E)NLNLNLLLL Apa...
Dugaan rekonstruksi mengatakan bahwa grafik (dengan setidaknya tiga simpul) ditentukan secara unik oleh subgraf yang dihapus dari verteks. Dugaan ini berusia lima dekade. Mencari literatur yang relevan, saya menemukan bahwa kelas grafik berikut diketahui dapat direkonstruksi: pohon grafik...
Lebar pohon mengukur seberapa dekat grafik dengan pohon. NP-hard untuk menghitung lebar pohon. Algoritma pendekatan yang paling dikenal mencapai faktor .O ( log n----√)HAI(logn)O(\sqrt{{\log}n}) Teorema Courcelle menyatakan bahwa setiap properti grafik yang dapat didefinisikan dalam logika orde...
Saya mencoba untuk menemukan seberapa dekat dan sebenarnya, ketika dan adalah konstanta yang tidak bergantung pada n (jadi ). Perkiraan saya adalah whp, tetapi saya belum dapat membuktikannya.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o...
Untuk konstanta , seseorang dapat menentukan dalam waktu linier, diberikan grafik input , apakah treewidth -nya adalah . Namun, ketika dan diberikan sebagai input, masalahnya adalah NP-hard. ( Sumber ). Gk ∈ Nk∈Nk \in \mathbb{N}GGGk G≤ k≤k\leq kkkkGGG Namun, ketika grafik input adalah planar ,...
Apakah ada yang tahu tentang program open-source untuk menghitung dekomposisi Tree dari grafik untuk "k" (lebar) yang diperbaiki? Saya tahu bahwa masalah menemukan Tree-Decomposition adalah NP-Hard untuk variabel "k", tetapi instance input saya akan sangat kecil (~ 10 node) dan "k" sudah...
Banyak masalah grafik yang sulit dipecahkan dalam waktu polinomial pada grafik treewidth terikat . Memang, buku teks biasanya menggunakan eg set independet sebagai contoh, yang merupakan masalah lokal . Secara kasar, masalah lokal adalah masalah yang solusinya dapat diverifikasi dengan memeriksa...
Saya ingin menghitung treewidth grafik. Ada heuristik yang benar-benar bagus untuk masalah grafik NP-hard lainnya seperti VF2 untuk subgraph isomorphism, dengan kode yang tersedia dalam igraph misalnya. Saya telah mencobanya pada grafik saya dan saya menemukan mereka berjalan sangat cepat untuk...
Treewidth memainkan peran penting dalam algoritma FPT, sebagian karena banyak masalah yang FPT parameter oleh treewidth. Gagasan terkait, lebih terbatas, adalah pathwidth. Jika grafik memiliki pathwidth , grafik juga memiliki treewidth paling banyak k , sedangkan pada arah sebaliknya, treewidth k...
Masalahnya Max-Sat meminta Anda untuk menemukan penugasan formula CNF yang memenuhi klausa sebanyak mungkin. Untuk masalah SAT yang lebih sederhana, ada banyak kasus khusus yang diketahui yang dapat diselesaikan dalam waktu polinomial, misalnya kita dapat menyelesaikan 2-SAT dalam waktu...
Pertanyaan ini mirip dengan salah satu pertanyaan saya sebelumnya. Hal ini diketahui bahwa adalah minor dilarang untuk grafik dari treewidth paling t .Kt + 2Kt+2K_{t+2}ttt Adakah keluarga yang dibangun dengan baik, parameter, dan tak terbatas grafik (selain grafik lengkap dan grafik kisi) yang...
Apakah kelas grafik berikut dikenal dalam literatur? Kelas grafik diparameterisasi dengan bilangan bulat positif dan dan berisi setiap grafik sedemikian rupa sehingga untuk setiap simpul , subgraf diinduksi pada semua simpul pada jarak paling banyak dari di memiliki treewidth paling banyak...
Saya mencari masalah yang termasuk ΣP2Σ2P\mathsf{\Sigma^P_2} dalam grafik umum tetapi dalam dalam grafik lebar pohon terbatas, Sebenarnya saya pikir masalah ini lebih sulit daripada menggunakan pemrograman dinamis normal dalam grafik terikat-treewidth untuk
Seperti diketahui, dekomposisi pohon pada grafik terdiri dari pohon dengan kantung terkait untuk setiap simpul , yang memenuhi kondisi berikut:T T v ⊆ V ( G ) v ∈ V ( T )GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Setiap simpul dari terjadi di beberapa kantong T .GGGTTT Untuk...
Ketika kita diberi dekomposisi pohon dari grafik dengan lebar , ada beberapa cara di mana kita dapat membuatnya "bagus". Secara khusus, diketahui bahwa adalah mungkin untuk mengubahnya menjadi dekomposisi pohon di mana pohon itu biner dan tingginya adalah . Ini dapat dicapai sambil menjaga lebar...
Mengingat grafik, G=(V,E)G=(V,E)G = (V, E) , saya ingin menemukan optimal rrr -domination untuk GGG . Artinya, saya ingin subset SSS dari sehingga semua simpul di berada pada jarak paling dari beberapa titik di , dan meminimalkan ukuran .G r S SVVVGGGrrrSSSSSS Dari apa yang saya periksa sejauh...
Saya tertarik pada grafik pada nnn simpul yang dapat diproduksi melalui proses berikut. Mulai dengan grafik arbitrer GGG pada k≤nk≤nk\le n simpul. Labeli semua simpul dalam sebagai tidak digunakan .GGG Menghasilkan grafik baru dengan menambahkan titik baru , yang terhubung ke satu atau lebih yang...
Satu dapat berbicara satu treewidth dari rangkaian Boolean, mendefinisikan sebagai treewidth dari "moralized" grafik pada kabel (simpul) yang diperoleh sebagai berikut: connect kabel dan setiap kali adalah output dari gerbang memiliki sebagai masukan (atau dan sebaliknya); sambungkan kabel dan...
Biarkan G menjadi pohon pada simpul 2n. The treewidth dari G, tw (G) = 1. Sekarang anggaplah kita menambahkan n edge ke G untuk mendapatkan grafik H. Batas atas yang mudah pada tw (H) adalah n + 1. Apakah ini pada dasarnya yang terbaik? Tampaknya entah bagaimana tw (H) harus O (sqrt (n)), tetapi...