Relaksasi LP set independen

13

Saya sudah mencoba relaksasi LP berikut set independen maksimum

max \sum_{i} x_{i}

$\max \sum_i x_i$

s.t. x_{i} + x_{j} \leq 1 \forall (i, j) \in E

$\text{s.t.}\ x_i+x_j\le 1\ \forall (i,j)\in E$

x_{i} \geq 0

$x_i\ge 0$

Saya mendapatkan $1/2$ untuk setiap variabel untuk setiap graf non-bipartit kubik aku mencoba.

Apakah benar untuk semua grafik non-bipartit kubik yang terhubung?
Apakah ada relaksasi LP yang bekerja lebih baik untuk grafik seperti itu?

Pembaruan 03/05 :

Inilah hasil relaksasi LP berbasis klik yang disarankan oleh Nathan

Saya telah meringkas eksperimen di sini. Menariknya, tampaknya ada beberapa grafik non-bipartit yang relaksasi LP paling sederhana adalah integral.

graph-theory co.combinatorics linear-programming Yaroslav Bulatov
sumber

Solusinya

tentu tidak unik. Dalam grafik bipartit kubik, Anda dapat memiliki solusi optimal dengan

di satu bagian dan

di bagian lain.

x_{i} = 1 / 2

$x_i = 1/2$

x_{i} = 1

$x_i = 1$

x_{i} = 0

$x_i = 0$

Jukka Suomela

1

Maaf, saya melewatkan bagian penting, saya menganggap grafik kubik non-bipartit saja. Setiap grafik kubik bipartit yang saya coba memiliki solusi integral

Yaroslav Bulatov

Anda juga perlu menambahkan "terhubung" jika Anda ingin menghindari solusi yang tidak unik.

Jukka Suomela

2

(1) Anda lupa menulis batasan nonnegativitas. (2) Untuk grafik bipartit, nilai optimal dari relaksasi LP ini selalu sama dengan ukuran maksimum dari set independen. Ini adalah akibat langsung dari teorema König .

Tsuyoshi Ito

2

@Yaroslav: Pertanyaan sampingan: bagaimana Anda menggambar grafik ini?

Tim

16

Non-bipartit terhubung grafik kubik memiliki solusi optimal yang unik ; dalam grafik kubik bipartit Anda memiliki solusi optimal yang tidak terpisahkan. $x_i = 1/2$

Bukti: Dalam grafik kubik, jika Anda menjumlahkan semua kendala , Anda memiliki , dan karenanya yang optimal paling banyak adalah . $3n/2$ $x_i + x_j \le 1$ $\sum_i 3 x_i \le 3n/2$ $n/2$

Solusinya untuk semua adalah sepele layak, dan karenanya juga optimal. $x_i = 1/2$ $i$

Dalam grafik kubik bipartit, setiap bagian memiliki setengah dari node, dan solusi dalam satu bagian karenanya juga optimal. $x_i = 1$

Setiap solusi yang optimal harus ketat, yaitu, kita harus memiliki dan karenanya untuk setiap tepi . Jadi jika Anda memiliki siklus yang aneh, Anda harus memilih untuk setiap node dalam siklus. Dan kemudian jika grafik terhubung, pilihan ini disebarkan ke mana-mana. $\sum_i 3 x_i = 3n/2$ $x_i + x_j = 1$ $\{i,j\}$ $x_i = 1/2$

Jukka Suomela
sumber

2

Seperti yang saya tulis dalam komentar pada pertanyaan, Anda hanya perlu bipartiteness untuk membuktikan keberadaan solusi optimal yang tidak terpisahkan (tetapi ini membutuhkan bukti yang berbeda dari Anda).

Tsuyoshi Ito

@ Tsuyoshi: Ya, teorema König baik untuk diingat. Sebagai contoh, bersama dengan pengamatan di atas, itu akan menunjukkan bahwa setiap grafik kubik bipartit memiliki 1-factorisation (yaitu, dapat dipartisi dalam tiga pencocokan sempurna). Tentu saja ini adalah cara "salah" untuk membuktikan hasil ini, tetapi saya pikir ini dengan baik menunjukkan kekuatan teorema König - jika Anda hanya ingat teorema König, ada banyak hasil klasik dalam teori grafik yang kemudian dapat Anda temukan kembali dengan mudah .

Jukka Suomela

12

LP ini setengah-integral untuk semua grafik, yaitu ada solusi optimal sehingga setiap variabel dalam {0,1 / 2,1}. Ini hanya mengikuti dari teorema Nemhauser dan Trotter. Tentu saja kesimpulan yang sama dari setengah-integralitas mengikuti untuk LP dari masalah komplemen (vertex cover). Ketika grafik adalah bipartit, solusinya integral. Ini mengikuti hanya dari teorema min-cut max-flow atau bekerja dengan solusi titik ekstrim dari LP ini. Juga, 1/2 tepi membentuk siklus aneh.

Tentu saja, LP ini tidak baik untuk menyelesaikan masalah IS. Menambahkan kendala Klik atau SDP adalah pendekatan yang jauh lebih baik.

Paket Vertex: sifat struktural dan algoritma GL Nemhauser dan Trotter-Math. Program., 1975

Mohit Singh
sumber

Benar, lihat juga Teorema 5.6 dari makalah ini untuk algoritma yang sangat sederhana yang efisien menemukan solusi setengah-integral.

Jukka Suomela

LP dengan kendala Clique memecahkan sekitar 50% lebih banyak grafik dari set di atas .... di mana saya dapat menemukan formulasi SDP?

Yaroslav Bulatov

7

Tesis Ph.D Sergiy Butenko dari tahun 2003 mengulas beberapa relaksasi LP MIS lainnya, serta beberapa relaksasi kuadratik.

Suresh Venkat
sumber

6

$K_4$

Ini disebut nomor himpunan bebas fraksional. Anda akan menemukan beberapa informasi di sana: http://en.wikipedia.org/wiki/Fractional_coloring atau dalam buku "Teori grafik pecahan" dari Daniel Ullman dan Edward Scheinerman ( http://www.ams.jhu.edu/~ers / fgt / ).

$K_k$ . Bagaimanapun, nilai hanya bisa menjadi "lebih representatif" dari nilai integer nyata (*) :-)

Nathann

(*) ini dikatakan, Anda secara teoritis memiliki perbedaan besar sewenang-wenang antara hasil optimal dalam LP di mana semua klik diwakili dan set independen optimal

Nathann Cohen
sumber

1

k

$k$

(k + 1)

$(k+1)$

x_{i} = 1 / k

$x_i = 1/k$

i

$i$

menarik, ini tampaknya terkait dengan kemudahan IndependentSet dalam grafik chordal

Yaroslav Bulatov

Saya melakukan beberapa percobaan, dan solusi dari relaksasi LP ini selalu integral dalam grafik chordal

Yaroslav Bulatov

1

@YaroslavBulatov Ada alasan untuk pengamatan Anda. Ketimpangan klik dan batas nonnegativitas menyediakan cembung set independen jika dan hanya jika grafik sempurna. Grafik chordal sempurna.

Austin Buchanan

Relaksasi LP set independen

Jawaban: