Algoritma Parametrized untuk Menemukan Bicliques

16

Diberikan simpul tak berarah titik, apa batas runtime paling dikenal untuk menemukan subgraph yang merupakan -biclique? Apakah ada algoritma parametrized yang lebih cepat daripada algoritma waktu dari "menebak" satu sisi biclique dan melihat apakah setidaknya ada simpul lain yang muncul pada semuanya? $n$ $k\times k$ $\binom{n}{k}\mbox{poly}(n)$ $k$

ds.algorithms reference-request graph-algorithms parameterized-complexity Andreas Björklund
sumber

8

Diparameterisasi oleh degenerasi atau keangkuhan, ini FPT. Lebih khusus lagi, mana adalah degenerasi (atau untuk arboricity). Lihat: $O(d^3 2^d n)$ $d$ $a^3 2^{2a}$

Algoritma daftar subgraph Arboricity dan bipartit. D. Eppstein. Inf. Proc Lett. 51: 207-211, 1994 .

Makalah berparameter lain baru saja diterima di SWAT 2012 , kali ini diparameterisasi dengan panjang jalur terinduksi terpanjang:

Aistis Atminas, Vadim Lozin dan Igor Razgon: Algoritma waktu linier untuk menghitung biclique kecil dalam grafik tanpa jalur yang panjang. SWAT 2012, muncul.

Tapi pemahaman saya adalah apakah ini FPT atau tidak dengan parameter alami (ukuran biclique) adalah masalah besar yang terbuka.

David Eppstein
sumber

David terima kasih Perhatikan bahwa saya tidak hanya bertanya-tanya apakah itu FPT wrt k, tetapi apakah ada sesuatu yang lebih baik daripada algoritma naif yang saya buat sketsa. Secara khusus, menemukan ternyata lebih mudah daripada menghitung.

Andreas Björklund

5

Makalah-makalah berikut ini menyediakan algoritma waktu-eksponensial untuk masalah biclique yang tidak diinduksi dan mungkin menarik bagi Anda:

Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Algoritma eksponensial-waktu yang tepat untuk menemukan bikli . Inf. Proses. Lett. 111 (2): 64-67 (2010)
Jean-François Couturier, Dieter Kratsch: Set
dan bicliques independen yang bersepeda . Inf. Proses. Lett. 112 (8-9): 329-334 (2012)

Limath
sumber

4

Perkiraan ini "Minimalisasi norma nuklir untuk klik yang ditanam dan masalah bikli", oleh B. Ames dan S. Vavasis ( http://arxiv.org/pdf/0901.3348.pdf ) menemukan biclique untuk beberapa jenis grafik pada poly- waktu, tetapi tidak memiliki jaminan perkiraan umum.

Para penulis menyusun kembali masalah biclique ke minimalisasi peringkat, tergantung pada batasan affine. Kemudian, mereka menyelesaikan relaksasi menggunakan heuristik norma nuklir, yang dapat dianggap sebagai SDP. Heuristik ini adalah gadget yang cukup menarik dari peralatan penginderaan terkompresi. Relaksasi ini biasanya mengakui beberapa kondisi optimalitas lucu ketika serangkaian kendala menunjukkan "jenis yang tepat" dari keacakan.

Dimitris
sumber

-1

$n^{o(k)}$

Elad
sumber

6

Saya pikir pengurangan ini tidak berhasil. Jika grafik awal Anda memiliki bikli besar di dalamnya, maka grafik yang Anda bentuk darinya (penutup ganda bipartitnya) akan tetap memiliki bikli yang sama, menutupi apakah grafik asli juga memiliki klik.

David Eppstein

Algoritma Parametrized untuk Menemukan Bicliques

Jawaban: