Seberapa mahal untuk menghancurkan semua jalur panjang dalam DAG?

Kami menganggap DAGs (diarahkan grafik asiklik) dengan satu node sumber $s$ dan satu sasaran simpul $t$ ; tepi paralel yang bergabung dengan pasangan simpul yang sama diizinkan. Sebuah $k$ - cut adalah satu set tepi yang removal menghancurkan semua $s$ - $t$ jalur lama dari $k$ ; jalur $s$ - lebih pendek $t$serta jalur "dalam" yang panjang (jalur yang tidak berada di antara $s$ dan $t$ ) dapat bertahan!

Pertanyaan: Apakah cukup untuk menghapus paling banyak sekitar $1/k$ bagian tepi dari DAG untuk menghancurkan semua jalur $s$ - $t$ lebih lama dari $k$ ?

Yaitu, jika $e(G)$ menunjukkan jumlah total tepi dalam $G$ , apakah setiap DAG $G$ memiliki $k$ -cut dengan paling banyak tentang $e(G)/k$ edge? Dua contoh:

1. Jika semua jalur $s$ - $t$ memiliki panjang $> k$ , maka potongan $k$ dengan tepi $\leq e(G)/k$ ada. Ini berlaku karena dengan demikian harus ada $k$ disjoint $k$ -cuts: hanya lapisan node $G$ sesuai dengan jaraknya dari node sumber $s$ .
2. Jika $G=T_n$ adalah turnamen transitif (DAG lengkap), maka juga $k$ potong dengan ada tepi: perbaiki urutan topologi node, pisahkan node menjadi interval panjang berturut-turut , dan hapus semua tepi yang bergabung dengan node dengan interval yang sama; ini akan menghancurkan semua jalur - lebih lama dari . $\leq k\binom{n/k}{2} \approx e(G)/k$n / k s t $k$$n/k$$s$$t$$k$

Catatan 1: Upaya naif untuk memberikan jawaban positif (yang juga saya coba pertama kali) adalah mencoba menunjukkan bahwa setiap DAG harus memiliki tentang $k$ disjoint $k$ -cuts. Sayangnya, Contoh 2 menunjukkan bahwa upaya ini bisa gagal: melalui argumen yang bagus, David Eppstein telah menunjukkan bahwa, untuk $k$ tentang $\sqrt{n}$ , grafik$T_n$tidak dapat memiliki lebih dari empatk-potong terputus ! $k$

Catatan 2: Adalah penting bahwa $k$ -cut hanya perlu menghancurkan semua panjang $s$ - $t$ jalan, dan belum tentu semua jalur panjang. Yaitu, ada ¹ DAGs di mana setiap "murni" $k$ potong (menghindari insiden tepi ke $s$ atau $t$ ) harus mengandung hampir semua tepi. Jadi, pertanyaan saya sebenarnya adalah: dapatkah kemungkinan untuk menghapus juga kejadian tepi dengan atau secara substansial mengurangi ukuran -cut? Kemungkinan besar, jawabannya negatif, tetapi saya belum menemukan contoh tandingan. t $s$$t$$k$

Motivasi: Pertanyaan saya termotivasi dengan membuktikan batas bawah untuk jaringan switching-and-rectifier monoton. Jaringan semacam itu hanyalah DAG, sebagian ujung-ujungnya diberi label oleh tes "is ?" (tidak ada tes ). The ukuran jaringan adalah jumlah sisi berlabel. Vektor input diterima, jika adax i = $x_i=1$$x_i=0$$s$ - semua tesnya konsisten dengan vektor ini. Markov telah membuktikan bahwa, jika fungsi boolean monoton f tidak memiliki minterm yang lebih pendek dari l dan tidak ada maxterm yang lebih pendek dari w , maka ukuran l ⋅ $t$$f$$l$$w$$l\cdot w$diperlukan. Jawaban positif untuk pertanyaan saya akan menyiratkan bahwa jaringan ukuran sekitar diperlukan, jika setidaknya w k variabel harus diatur ke 0 untuk menghancurkan semua minterm lebih lama dari k .$k\cdot w_k$$w_k$$0$$k$

¹ Konstruksi diberikan dalam makalah ini. Ambil pohon biner dari log kedalaman n . Hapus semua tepi. Untuk setiap simpul dalam v , menggambar tepi untuk v dari setiap daun dari subtree kiri T v , dan tepi dari v ke setiap daun dari subtree kanan T v . Dengan demikian, setiap dua daun T dihubungkan oleh jalur panjang 2 di DAG. DAG itu sendiri memiliki ∼ n node dan ∼ n log n edge, tetapi Ω ( $T$$\log n$$v$$v$$T_v$$v$$T_v$$T$$2$$\sim n$$\sim n\log n$ tepi harus dihilangkan untuk menghancurkan semua jalur yang lebih panjang dari$\Omega(n\log n)$ .$\sqrt{n}$

[Jawab sendiri; ini adalah versi singkat, yang lama dapat ditemukan di sini ]

Kami menyadari dengan Georg Schnitger bahwa jawaban untuk pertanyaan saya sangat negatif : ada DAG (bahkan dengan derajat konstan), di mana setiap potongan harus memiliki fraksi yang konstan dari semua sisi, bukan hanya fraksi sekitar 1 / k , seperti pada pertanyaan saya. (Hasil yang sedikit lebih lemah bahwa fraksi 1 / log k mungkin diperlukan dapat diperoleh dengan menggunakan konstruksi yang lebih sederhana yang disebutkan dalam catatan kaki di atas. Tulisan cepat ada di sini ) $k$$1/k$$1/\log k$

Yaitu, dalam makalah "Pada pengurangan kedalaman dan gerbang" , Georg membuat urutan grafik asiklik terarah dari derajat maksimum konstan d pada n = m 2 m node dengan properti berikut:$H_n$$d$$n=m2^m$

• Untuk setiap konstan ada konstan c > 0 sehingga, jika ada bagian dari paling c n node dihapus dari H n , grafik yang tersisa mengandung jalur panjang setidaknya 2 ε m . $0\leq \epsilon < 1$$c > 0$$cn$$H_n$$2^{\epsilon m}$

Ambil sekarang dua simpul baru dan t , dan gambarlah tepi dari s ke setiap simpul H n , dan satu tepi dari setiap simpul H n ke t . Grafik yang dihasilkan G n masih memiliki paling banyak 2 n + d n = O ( n ) edge.$s$$t$$s$$H_n$$H_n$$t$$G_n$$2n+dn=O(n)$

Untuk setiap konstan , ada konstan c ' > 0 sehingga, jika ada bagian dari paling c ' n tepi dihapus dari G n , grafik tersisa berisi s - t jalan dengan 2 ε m atau lebih banyak tepi. $0\leq \epsilon < 1$$c ' > 0$$c'n$$G_n$$s$$t$$2^{\epsilon m}$

Bukti: Panggil simpul simpul dalam G n . Hapus subset paling banyak dari c ′ n edge dari G n , di mana c ′ = c / 2 . Setelah itu, lepaskan simpul bagian dalam jika itu insiden ke tepi yang dihapus. Perhatikan bahwa paling 2 c ' n = c n node dalam kemudian dihapus. Tak satu pun dari insiden tepi ke node yang selamat telah dihapus. Secara khusus, setiap simpul dalam yang selamat masih terhubung ke kedua simpul s dan $H_n$ $G_n$$c'n$$G_n$$c'=c/2$$2c'n=cn$$s$$t$. Dengan properti di atas dari , harus tetap ada jalan dengan panjang 2 ϵ m yang seluruhnya terdiri dari simpul-simpul dalam yang selamat. Karena titik akhir dari masing-masing jalur ini bertahan, masing-masing dapat diperpanjang ke jalur s - t di G n . QED$H_n$$2^{\epsilon m}$$s$$t$$G_n$

Konsekuensinya menyedihkan: tidak ada analog apapun dari lemma Markov untuk fungsi dengan banyak minterm pendek , meskipun set minterm panjang memiliki beberapa struktur "rumit": tidak ada batas bawah super-linier pada ukuran jaringan yang kemudian dapat dibuktikan menggunakan argumen "panjang kali lebar" ini.

PS Argumen "panjang kali lebar" ini (ketika semua jalur - t cukup panjang) sebelumnya digunakan oleh Moore dan Shannon (1956). Satu-satunya perbedaan adalah bahwa mereka tidak diizinkan memperbaiki (tepi berlabel). Jadi, ini sebenarnya adalah "argumen Moore-Shannon-Markov".$s$$t$