Keuntungan algoritmik dari jalur lebar dibandingkan treewidth

Treewidth memainkan peran penting dalam algoritma FPT, sebagian karena banyak masalah yang FPT parameter oleh treewidth. Gagasan terkait, lebih terbatas, adalah pathwidth. Jika grafik memiliki pathwidth , grafik juga memiliki treewidth paling banyak , sedangkan pada arah sebaliknya, treewidth hanya menyiratkan pathwidth di sebagian besar dan ini ketat. $k$ $k$ $k$ $k\log n$

Mengingat hal di atas, orang mungkin berharap bahwa mungkin ada keuntungan algoritmik yang signifikan untuk grafik jalur terbatas. Namun, tampaknya sebagian besar masalah yang merupakan FPT untuk satu parameter adalah FPT untuk yang lainnya. Saya ingin tahu mengetahui ada contoh tandingan untuk ini, yaitu, masalah yang "mudah" untuk pathwidth tetapi "sulit" untuk treewidth.

Izinkan saya menyebutkan bahwa saya termotivasi untuk mengajukan pertanyaan ini dengan membuka makalah baru-baru ini oleh Igor Razgon ("Pada OBDD untuk CNFs dari treewidth terikat", KR'14) yang memberikan contoh masalah dengan solusi ketika adalah pathwidth dan (kira-kira) batas bawah ketika adalah treewidth. Saya bertanya-tanya apakah ada spesimen lain dengan perilaku ini. $2^{k}n$ $k$ $n^k$ $k$

Rangkuman: Apakah ada contoh masalah alam yang W-hard parameterkan oleh treewidth tetapi FPT parameterisasi oleh pathwidth? Secara lebih luas, apakah ada contoh masalah yang kompleksitasnya diketahui / diyakini jauh lebih baik ketika diparameterisasi oleh pathwidth alih-alih treewidth?

parameterized-complexity treewidth graph-minor Michael Lampis
sumber

Ada masalah yang mudah di jalan tetapi NP-Hard di pohon. Ini termasuk multicut minimum dan multiflow integer maksimum.

Chandra Chekuri

@ChandraChekuri Ini adalah poin yang bagus, tetapi apakah algoritma untuk path untuk masalah seperti itu biasanya digeneralisasi ke pathwidth? Sebagai contoh, untuk multiflow max integer, saya pikir ini tidak terjadi. Garg, Vazirani dan Yannakakis membuktikan NP-hardness untuk pohon dalam "algoritma pendekatan Primal-dual untuk aliran integral dan multicut di pohon". Reduksi di sana menggunakan pohon tinggi 3. Ini berarti bahwa masalahnya adalah NP-hard untuk jalur konstan.

Michael Lampis

Sekali lagi ini bukan jawaban bersih untuk pertanyaan awal. Kesenjangan aliran-potong dalam grafik pathwidth k diketahui dibatasi oleh f (k) untuk beberapa fungsi f melalui hasil dari Lee dan Sidiropoulos. Merupakan masalah terbuka yang penting apakah hasil seperti itu berlaku untuk treewidth. Kasing k = 3 terbuka untuk treewidth.

Chandra Chekuri

Algoritma terbaik untuk Hamiltonian Cycle yang diparameterisasi oleh pathwidth memiliki runtime

(arxiv.org/abs/1211.1506) sedangkan treewidth terbaik adalah

(arxiv.org/abs/1103.0534) Namun, ini mungkin hanya celah yang menunggu untuk ditutup.

(2 + \sqrt{2})^{p w}

$(2+\sqrt{2})^{pw}$

4^{t w}

$4^{tw}$

daniello

Terlihat bahwa [1] Mixed Chinese Postman Problem (MCPP) yang diparameterisasi oleh pathwidth adalah -hard, bahkan jika semua tepi dan busur dari grafik input memiliki bobot dan FPT sehubungan dengan treedepth. Ini adalah masalah pertama yang disadari telah terbukti sebagai -tidak keras sehubungan dengan treewidth tetapi FPT sehubungan dengan treedepth. Perhatikan bahwa jalur lebar grafik terletak di antara treewidth dan treedepth. $W[1]$ $G$ $1$ $W[1]$

The Steiner Multicut masalah, yang bertanya, diberikan sebuah grafik diarahkan , koleksi , , set terminal ukuran paling , dan integer , apakah ada satu set paling banyak tepi atau node sehingga setiap set setidaknya satu sepasang terminal dalam komponen terhubung yang berbeda dari . $G$ $T = \{T_1, . . . , T_t\}$ $T_i ⊆ V(G)$ $p$ $k$ $S$ $k$ $T_i$ $G \ S$

Node Steiner Multicut, Edge Steiner Multicut, dan Restr. Node Steiner Multicut adalah -Hard untuk parameter , bahkan jika dan [2]. $W[1]$ $k$ $p = 3$ $tw(G) = 2$

[1] https://core.ac.uk/download/pdf/77298274.pdf

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf

Rupei Xu
sumber

Keuntungan algoritmik dari jalur lebar dibandingkan treewidth

Jawaban: