Parametriisasi ganda yang tidak standar dari masalah grafik

Salah satu hasil mendasar dalam kompleksitas parameter dari masalah grafik adalah bahwa COVER VERTEX di-parameterisasi oleh ukuran solusi adalah fixed-parameter-trable (FPT). Di sisi lain, ketika diparameterisasi oleh "parameter ganda" , itu menjadi setara dengan SET INDEPENDEN diparameterisasi oleh ukuran solusi (karena setiap penutup simpul adalah pelengkap set independen), dan karenanya W [1] -hard.| V ( G ) | - $k$$|V(G)|-k$

Meskipun ini tampak kurang alami, saya tertarik pada kompleksitas parameter VERTEX COVER untuk parameter . Ini adalah parameter yang lebih besar dari . Apakah VERTEX COVER FPT untuk parameter ini?| V ( G ) | - $|E(G)|-k$$|V(G)|-k$

Catatan: Saya juga tertarik pada parameterisasi serupa untuk masalah grafik lainnya (mis. SET DOMINASI). Satu-satunya tempat di mana saya telah melihat kedua jenis parameter ganda yang dipelajari adalah untuk masalah hypergraph TEST COVER dalam makalah 2012 " Studi Parameterisasi dari Masalah Cover Test " oleh Crowston, Gutin, Jones, Saurabh dan Yeo. (juga di arXiv )

Sunting (04/12/2016): Parameterisasi ini juga dipelajari untuk masalah hypergraph lainnya HITTING SET dalam 2011 paper Kernels untuk parameterisasi di bawah-batas dari hitting set dan diarahkan untuk mengatur masalah himpunan oleh Gutin, Mones dan Yeo ( arXiv tautan ).

Biarkan dan m : = | E ( G ) | . Parameter ganda m - k selalu paling tidak sebesar m - n yang pada gilirannya setidaknya sebesar ukuran set tepi umpan balik, seperangkat tepi yang penghapusannya membuat G asiklik.$n:=|V(G)|$$m:= |E(G)|$$m-k$$m-n$$G$

Ukuran set tepi umpan balik terkecil, sebut saja nomor tepi umpan balik , juga setidaknya sama besar dengan nomor simpul umpan balik dan treewidth grafik. Ini secara langsung menyiratkan bahwa Penutup Vertex adalah traktat dengan parameter tetap untuk m - k . Selain itu, ia memiliki kernel polinomial karena Vertex Cover parameterisasi oleh umpan balik nomor vertex memiliki satu (ini ditunjukkan oleh Jansen dan Bodlaender di Vertex Cover Kernelization Revisited - Batas Atas dan Bawah untuk Parameter yang Diperbaiki. Teori Komputasi. Sistem 53 (2): 263-299 (2013), http://dx.doi.org/10.1007/s00224-012-9393-4 ).$\phi$$m-k$

Kernel linear langsung sederhana untuk Vertex Cover yang diparameterisasi dengan nomor edge umpan balik harus dapat diperoleh sebagai berikut: Hapus semua simpul derajat-0, tambahkan tetangga simpul derajat-1 apa pun ke penutup simpul, dan kurangi jalur simpul derajat-2 yang mengandung setidaknya 2 simpul (mengurangi batas pada k sesuai). Setelah penerapan yang lengkap dari aturan reduksi ini, pada grafik yang dihasilkan n = O ( ϕ ) . Ini secara langsung menyiratkan kernel untuk parameter yang lebih besar m - k .$\phi$$k$$n=O(\phi)$$m-k$

Untuk menjawab pertanyaan Anda untuk referensi: Saya akan mencari nomor edge umpan balik yang lebih kecil dari parameter ganda , telah dipertimbangkan dalam literatur, dan sering memberikan hasil traktabilitas parameter tetap juga untuk Dominating Set (karena parameternya cukup besar). Berikut adalah tiga contoh lebih lanjut:$m-k$

Johannes Uhlmann, Mathias Weller: Planarisasi Dua-Lapisan diparameterisasi oleh set edge umpan balik. Teor Komputasi. Sci. 494: 99-111 (2013), http://dx.doi.org/10.1016/j.tcs.2013.01.029

André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller: Pada kasus yang dapat ditelusuri, Pemilihan Target Set. Jejaring Sosial Analis. Penambangan 3 (2): 233-256 (2013), http://dx.doi.org/10.1007/s13278-012-0067-7

Sepp Hartung, Christian Komusiewicz, André Nichterlein: Algoritma Parameter dan Eksperimen Komputasi untuk Menemukan 2-Klub. J. Grafik Algoritma Appl. 19 (1): 155-190 (2015), http://dx.doi.org/10.7155/jgaa.00352

$2k+1$$G'$$|E(G')|\le |E(G)|-2k$$G'$$|E(G')|$$|E(G)|-k$$G$

$2k+1$$2k+1$$2k$