Konektivitas grafik oleh penghapusan tepi dan simpul

Mari kita mengatakan bahwa grafik adalah -connected jika penghapusan setiap simpul dan setiap tepi dari daun selalu graf terhubung. Misalnya, grafik -connect, sesuai dengan definisi standar, adalah -connected, sesuai dengan definisi baru. Apakah ada algoritma polinomial-waktu untuk memutuskan apakah adalah -connected? Di sini saya menganggap bahwa inputnya adalah , dan . $G$ $(a,b)$ $a$ $b$ $G$ $k$ $(k-1,0)$ $G$ $(a,b)$ $G$ $a$ $b$

ds.algorithms graph-theory graph-algorithms some one
sumber

Masalah pekerjaan rumah?

Chandra Chekuri

Saya sampai pada pertanyaan ini saat berbicara dengan Janez Zerovnik tentang konektivitas jaringan sekitar 2/3 tahun. Sejujurnya, saya tidak ingat detailnya. Sejak itu, saya telah bertanya tentang 4 peneliti dan tidak ada yang melihat bagaimana menguranginya menjadi konektivitas titik (atau konektivitas tepi), yang akan menjadi pendekatan yang jelas. Juga, tidak ada yang bisa menunjukkan teorema tipe-Menger. Jadi ya, saya pikir ini adalah pertanyaan tingkat penelitian, mungkin dengan jawaban sederhana atau tidak.

seseorang

Saya tidak tahu mengapa orang terkadang menganggap pertanyaan adalah pekerjaan rumah tanpa memikirkannya terlebih dahulu. Saya pikir Anda tidak boleh menyatakan sesuatu pekerjaan rumah kecuali setidaknya Anda tahu bagaimana menyelesaikannya.

domotorp

@domotorp: orang biasanya bertanya apakah itu pekerjaan rumah, bukan klaim. Sulit untuk menilai apakah suatu pertanyaan adalah tingkat pekerjaan rumah atau tidak ketika pertanyaan itu tidak mengandung latar belakang / motivasi.

Kaveh

Saya mengerti bahwa pertanyaan saya dapat disalahartikan sebagai pekerjaan rumah karena beberapa alasan, tetapi sekarang kita harus melanjutkan. Sebenarnya, dengan komentar Chandra Chekuri saya mendapat harapan bahwa mungkin pertanyaannya mungkin memiliki jawaban sederhana ...

seseorang

Jawaban:

Ini adalah versi yang diedit dari "jawaban" sebelumnya yang secara tidak benar mengklaim algoritma polinomial-waktu untuk masalah tersebut. Apa yang saya tulis di bawah ini adalah koneksi ke masalah yang ada yang menunjukkan bahwa masalahnya sulit.

Misalkan adalah dua simpul dalam dan kami ingin memeriksa apakah keduanya terhubung . Yang menghapus setiap node dan setiap tepi seharusnya tidak disconnect dan . Cara lain untuk melihatnya adalah sebagai berikut: berapa jumlah minimum node yang perlu kita hapus untuk mengurangi konektivitas edge antara dan ke $s,t$ $G$ $(a,b)$ $a$ $b$ $s$ $t$ $s$ $t$ $b$ ? Jenis-jenis masalah ini telah dipelajari dengan nama pemotongan multi-rute dan mereka merupakan aliran rangkap untuk multi-rute. Berbagai hasil pendekatan telah ditunjukkan meskipun banyak masalah dasar belum terselesaikan. Hasil yang menarik adalah sebagai berikut. Misalkan setiap sisi memiliki biaya dan kami ingin menghapus set tepi biaya minimum untuk mengurangi konektivitas tepi antara dan ke ; maka masalah ini adalah NP-Hard ketika adalah bagian dari input. Hasil ini di koran oleh Barman dan Chawla: http://arxiv.org/abs/0908.0350 $c(e)$ $s$ $t$ $b$ $b$

Dua makalah yang akan muncul dalam SODA 2012 mendatang adalah pemotongan multi-rute yang memiliki hasil lebih lanjut pada topik. Yang oleh Chuzhoy etal memiliki hasil kekerasan untuk beberapa varian.

Chandra Chekuri
sumber

Kertas etal Chuzhoy sekarang tersedia di ArXiv: arxiv.org/abs/1112.3611

Chandra Chekuri