Fungsi menarik pada grafik yang dapat dimaksimalkan secara efisien.

Katakanlah saya memiliki grafik berbobot sedemikian rupa sehingga adalah fungsi pembobotan - perhatikan bahwa bobot negatif diperbolehkan.w : E → [ - 1 , 1 $G = (V,E,w)$$w:E\rightarrow [-1,1]$

Mengatakan bahwa mendefinisikan properti dari setiap bagian dari simpul . S ⊂ $f:2^V\rightarrow \mathbb{R}$$S \subset V$

Pertanyaan: Apa sajakah contoh menarik dari s yang masalah maksimasinya: dapat dilakukan dalam waktu polinomial?arg maks S ⊆ V f ( S $f$$\arg\max_{S \subseteq V}f(S)$

Misalnya, fungsi pemotongan grafik

Saya akan membiarkan definisi "menarik" agak kabur, tetapi saya ingin masalah maksimisasi menjadi non-sepele. Misalnya, Anda tidak boleh menentukan jawabannya tanpa memeriksa tepi grafik (fungsi yang konstan, dan fungsi kardinalitas tidak menarik). Seharusnya juga tidak menjadi kasus bahwa $f$ benar-benar hanya menyandikan beberapa fungsi lain dengan domain berukuran polinomial dengan memasukkannya ke dalam domain $2^V$ (yaitu saya tidak ingin ada beberapa domain kecil $X$ , dan beberapa fungsi $m:2^S\rightarrow X$ diketahui sebelum melihat grafik, sehingga fungsi yang diinginkan benar-benar $g:X\rightarrow \mathbb{R}$ , dan $f(S) = g(m(S))$ Jika ini masalahnya, maka masalah "maksimalisasi" sebenarnya hanya masalah mengevaluasi fungsi pada semua input.)

Sunting: Memang benar bahwa kadang-kadang masalah minimisasi mudah jika Anda mengabaikan bobot tepi (meskipun tidak meminimalkan fungsi pemotongan, karena saya mengizinkan bobot tepi negatif). Tapi saya secara eksplisit tertarik pada masalah maksimisasi. Itu tidak menjadi masalah dalam masalah alami dalam pengaturan ini.

Setiap kali menghitung jumlah sisi memenuhi beberapa predikat Boolean yang didefinisikan dalam istilah dan , maka apa yang Anda tulis hanyalah Boolean 2-CSP. Fungsi obyektif meminta untuk memaksimalkan jumlah klausa yang puas atas semua penugasan ke variabel. Ini dikenal sebagai NP-hard dan ambang kekerasan yang tepat juga diketahui dengan asumsi UGC (lihat Raghavendra'08).( u , v ) u ∈ S v ∈ $f(S)$$(u,v)$$u\in S$$v\in S$

Ada banyak contoh positif alami ketika Anda ingin memaksimalkan subset tepi, misalnya, Pencocokan maksimum adalah salah satu contoh masalah waktu polinomial dalam kasus ini.

Partisi otomatis / lemah 2 warna.

(Dalam hal ini jika setiap v ∈ S memiliki tetangga dalam V ∖ S dan sebaliknya. Sebaliknya f ( S ) = 0. Solusi dengan f ( S ) = 1 selalu ada jika tidak ada yang terisolasi node, dan dapat ditemukan dengan mudah dalam waktu polinomial.)$f(S) = 1$$v \in S$$V \setminus S$$f(S) = 0$$f(S) = 1$

Minimum cut (khusus, vertex cut).

(Dalam hal ini akan menjadi sesuatu seperti ini: 0 jika menghapus node di set S tidak mempartisi G dalam setidaknya dua komponen, dan | V | - | S | sebaliknya. Kemudian memaksimalkan f setara dengan mencari potongan minimum , yang dapat dilakukan dalam waktu polinomial.)$f$$S$$G$$|V| - |S|$$f$

Anda juga dapat mendefinisikan fungsi serupa yang sesuai dengan pemotongan tepi minimum.

(Misalnya, adalah 0 jika S = ∅ atau S = V ; jika tidak | E | - | X | , di mana X adalah himpunan tepi yang memiliki satu titik akhir dalam S dan titik akhir lainnya di V ∖ S. )$f(S)$$S = \emptyset$$S = V$$|E| - |X|$$X$$S$$V \setminus S$

Set independen maksimal.

(Di sini = jumlah node dalam S yang tidak berdekatan dengan node lain di S + jumlah node dalam V ∖ S yang berdekatan dengan node di S. Iff S adalah set independen maksimal yang kita miliki f ( S ) = | V | .)$f(S)$$S$$S$$V \setminus S$$S$$S$$f(S) = |V|$