Apakah kerumitan masalah jalur ini diketahui?

Instance: Grafik tidak berarah $G$ dengan dua simpul dibedakan $s\neq t$ , dan integer $k\geq 0$ .

Pertanyaan: Apakah terdapat sebuah $s-t$ jalan di $G$ , sehingga berpotongan jalan paling $k$ segitiga? (Untuk masalah ini, sebuah jalur dikatakan memotong segitiga jika jalur tersebut mengandung setidaknya satu sisi dari segitiga.)

cc.complexity-theory graph-algorithms Andras Farago
sumber

Apakah ini salah? Kami menetapkan bobot untuk setiap sisi dan kemudian kami menemukan jalur st terpendek. Berat setiap tepi adalah jumlah segitiga yang termasuk tepi itu. Berat jalur ini tidak sama dengan jumlah segitiga yang bertemu tetapi itu adalah jalur st dengan jumlah segitiga minimum. (Masalah yang mungkin adalah bahwa kita dapat menghitung satu atau lebih segitiga dua kali karena kita mengunjungi dua sisi segitiga itu tetapi alasan mengapa kita memilihnya adalah bahwa mereka lebih kecil daripada melalui sisi lain dari segitiga dan juga kita memiliki cara jalur sederhana dua sisi segitiga bersebelahan).

Saeed

@ Saeed Saya tidak mengerti: apa argumen bahwa penghitungan yang berlebihan tidak membuat Anda memilih jalur yang tidak optimal? Algoritme Anda tentu merupakan 2 perkiraan Mungkin perbaikannya adalah menambahkan tepi

untuk setiap jalur

dengan bobot sama dengan jumlah segitiga yang mengandung keduanya

dan

(u, w)

$(u, w)$

u \to v \to w

$u\to v \to w$

(u, v)

$(u,v)$

(v, w)

$(v,w)$

Sasho Nikolov

Benar, kita dapat pergi dari u ke v dan kemudian kita memilih x (beberapa simpul lain tidak dalam segitiga uvw) maka kita pergi ke w yang salah (kesalahan saya adalah bahwa saya terjawab di antara simpul yang tidak ada di segitiga uvw) , tetapi dengan perbaikan Anda itu benar karena untuk setiap jalur st dengan segitiga

dalam grafik asli ada jalur bobot

dalam grafik tambahan. Lebih lanjut, berat lintasan dalam grafik baru selalu paling tidak sebagai jumlah segitiga dalam lintasan yang sesuai dalam grafik asli.

α

$\alpha$

α

$\alpha$

Saeed

Saya memberikan sedikit lebih banyak pemikiran tentang hal itu, bahkan setelah memperbaikinya tidak berhasil. Maaf Andras jika saya membawa harapan yang salah. Untuk melihat mengapa memperbaiki yang salah menganggap simpul

di jalan

dan kami memiliki segitiga

u - > v - > w - > x

$u->v->w->x$

P

$P$

dan

dan misalkan tepian

dan

adalah kebetulan juga banyak segitiga. Jika kita menggunakan tepi baru buatan yang menghubungkan

maka kita menghitung segitiga

u, v, w

$u,v,w$

v, w, x

$v,w,x$

v x

$vx$

u w

$uw$

u - > w

$u->w$

dua kali. PS: Alasan saya lagi salah karena saya pikir kita cukup mengganti

dan

dengan baru (multi) edge

. Jika kita menambahkan tepi buatan itu untuk setiap jalur, itu akan bekerja sepele. Sepertinya itu NPC.

v, w, x

$v,w,x$

u - > v

$u->v$

v - > w

$v->w$

u - > w

$u->w$

Saeed

Gagasan saya tidak akan berfungsi - saya harus mempertahankan beberapa set, dan saya pikir akan ada terlalu banyak.

reinierpost

Menganggap tidak ada self-tepi di . $G$

Untuk setiap tepi antara simpul dan di , misalkan , dan jika tidak ada tepi. Hitung matriks $v_i$ $v_j$ $G$ $E[i,j]=1$ $E[i,j]=0$ $n\times n$ , yang memberikan jumlah jalur dua-hop antara masing-masing pasangan node dan . Kemudian untuk edge antara dan dalam menghitung jika tidak maka set $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$ $v_i$ $v_j$ $v_i$ $v_j$ $G$ $D[i,j]=E[i,j]\cdot C[i,j]$ $D[i,j]=\infty$ , Yang memberi jumlah segitiga tepi adalah bagian dari (atau tak terhingga jika tidak ada tepi). Penggandaan matriks yang diperlukan untuk menghitung biaya (dapat dihitung lebih cepat tergantung pada tingkat ). $C$ $O(n^3)$ $G$

Sekarang hitung matriks , sedemikian sehingga $n\times n$ $A$ . adalah semua jalur terpendek di $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$ $A$ $D$ panjang hingga dua ditambah untuk menjelaskan jalur yang melewati dua sisi beberapa segitiga.

Sekarang cukup hitung lintasan terpendek antara dan dalam pada grafik baru yang adalah matriks adjacency (tertimbang) menggunakan Dijkstra (karena semua bobot tepi positif) yaitu dan tentukan apakah $v_i$ $v_j$ $G$ $A$ , di mana adalah penutupan semiring tropis (yang memberikan matriks jarak). $A^*[i,j]\leq k$ $A^*$

Edgar
sumber

Apakah kerumitan masalah jalur ini diketahui?

Jawaban: